Minimum Link Fencing

Authors Sujoy Bhore , Fabian Klute , Maarten Löffler, Martin Nöllenburg , Soeren Terziadis , Anaïs Villedieu



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.34.pdf
  • Filesize: 1.3 MB
  • 14 pages

Document Identifiers

Author Details

Sujoy Bhore
  • Department of Computer Science & Engineering, Indian Institute of Technology Bombay, India
Fabian Klute
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Maarten Löffler
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Martin Nöllenburg
  • Algorithms and Complexity Group, TU Wien, Austria
Soeren Terziadis
  • Algorithms and Complexity Group, TU Wien, Austria
Anaïs Villedieu
  • Algorithms and Complexity Group, TU Wien, Austria

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 AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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. Google Scholar
  4. 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.
  5. Gautam Das. Approximation schemes in computational geometry. PhD thesis, University of Wisconsin, Madison, 1991. Google Scholar
  6. 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.
  7. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. Cao An Wang. Finding minimal nested polygons. BIT Computer Science section, 31(2):230-236, 1991. URL: https://doi.org/10.1007/BF01931283.
  14. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail