LIPIcs.ISAAC.2022.34.pdf
- Filesize: 1.3 MB
- 14 pages
Document
Minimum Link Fencing
Authors
Sujoy Bhore 
,
Fabian Klute ,
Martin Nöllenburg ,
Soeren Terziadis ,
Anaïs Villedieu
-
Part of:
Volume:
33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
- Department of Computer Science & Engineering, Indian Institute of Technology Bombay, India
Acknowledgements
The authors would like to thank Thekla Hamm and Irene Parada for the valuable discussion in particular concerning the XP results of Section 3.
Cite As Get BibTex
Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum Link Fencing. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.34
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- computational geometry
- polygon nesting
- polygon separation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, and Mikkel Thorup. Fast fencing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 564-573, 2018. URL: https://doi.org/10.1145/3188745.3188878.
- Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric multicut. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 9:1-9:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.9.
-
Alok Aggarwal, Heather Booth, Joseph O'Rourke, Subhash Suri, and Chee-Keng Yap. Finding minimal convex nested polygons. Information and Computation, 83(1):98-110, 1989.
- Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum link fencing, 2022. URL: http://arxiv.org/abs/2209.14804.
-
Gautam Das. Approximation schemes in computational geometry. PhD thesis, University of Wisconsin, Madison, 1991.
- Peter Eades and David Rappaport. The complexity of computing minimum separating polygons. Pattern Recognition Letters, 14(9):715-718, 1993. URL: https://doi.org/10.1016/0167-8655(93)90140-9.
- Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
- Michael R Garey, Ronald L Graham, and David S Johnson. The complexity of computing steiner minimal trees. SIAM journal on applied mathematics, 32(4):835-859, 1977. URL: https://doi.org/10.1137/0132072.
- Subir Kumar Ghosh. Computing the visibility polygon from a convex set and related problems. Journal of Algorithms, 12(1):75-95, 1991. URL: https://doi.org/10.1016/0196-6774(91)90024-S.
- John Hershberger and Jack Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4:63-97, 1994. URL: https://doi.org/10.1016/0925-7721(94)90010-8.
- Klaus Jansen and Haiko Müller. The minimum broadcast time problem for several processor networks. Theoretical Computer Science, 147(1-2):69-85, 1995. URL: https://doi.org/10.1016/0304-3975(94)00230-G.
- Joseph SB Mitchell and Subhash Suri. Separation and approximation of polyhedral objects. Computational Geometry: Theory and Applications, 5(2):95-114, 1995. URL: https://doi.org/10.1016/0925-7721(95)00006-U.
- Cao An Wang. Finding minimal nested polygons. BIT Computer Science section, 31(2):230-236, 1991. URL: https://doi.org/10.1007/BF01931283.
- Cao An Wang and Edward P. F. Chan. Finding the minimum visible vertex distance between two non-intersecting simple polygons. In Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, Yorktown Heights, NY, USA, June 2-4, 1986, pages 34-42. ACM, 1986. URL: https://doi.org/10.1145/10515.10519.