<div class="csl-bib-body">
<div class="csl-entry">Bhore, S., Klute, F., Löffler, M., Nöllenburg, M., Terziadis, S., & Villedieu, A. (2022). Minimum Link Fencing. In <i>33rd International Symposium on Algorithms and Computation (ISAAC 2022)</i> (pp. 34:1-34:14). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2022.34</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/161631
-
dc.description.abstract
We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.
en
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.relation.isversionof
10.48550/arXiv.2209.14804
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
computational geometry
en
dc.subject
polygon nesting
en
dc.subject
polygon separation
en
dc.title
Minimum Link Fencing
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.relation.publication
33rd International Symposium on Algorithms and Computation (ISAAC 2022)