LIPIcs.ICALP.2019.9.pdf
- Filesize: 0.61 MB
- 15 pages
Document
Geometric Multicut
Authors
Mikkel Abrahamsen 
,
Günter Rote
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Author Details
Acknowledgements
This work was initiated at the workshop on Fixed-Parameter Computational Geometry at the Lorentz Center in Leiden in May 2018. We thank the organizers and the Lorentz Center for a nice workshop and Michael Hoffmann for useful discussions during the workshop.
Cite As Get BibTex
Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric Multicut. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.9
Abstract
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2-4/3k)-approximation algorithm.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
- Theory of computation → Computational geometry
Keywords
- multicut
- clustering
- Steiner tree
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: http://dx.doi.org/10.1145/3188745.3188878.
- Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric multicut, 2019. URL: http://arxiv.org/abs/1902.04045.
- Oswin Aichholzer and Franz Aurenhammer. Straight skeletons for general polygonal figures in the plane. In Jin-Yi Cai and Chak Kuen Wong, editors, Computing and Combinatorics (COCOON 1996), volume 1090 of Lecture Notes in Computer Science, pages 117-126. Springer-Verlag, 1996. URL: http://dx.doi.org/10.1007/3-540-61332-3_144.
-
Oswin Aichholzer and Franz Aurenhammer. Straight skeletons for general polygonal figures in the plane. In A. Samoilenko, editor, Voronoi’s Impact on Modern Sciences, Vol. II, volume 21 of Proceedings of the Institute of Mathematics of the National Academy of Sciences of Ukraine, pages 7-21. Institute of Mathematics of the National Academy of Sciences of Ukraine, Kiew, 1998.
- Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM Journal on Computing, 46(4):1280-1303, 2017. URL: http://dx.doi.org/10.1137/15M1042929.
- Gruia Călinescu, Howard Karloff, and Yuval Rabani. An improved approximation algorithm for Multiway Cut. Journal of Computer and System Sciences, 60(3):564-574, 2000. URL: http://dx.doi.org/10.1006/jcss.1999.1687.
- Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39(1):1-54, 1992. URL: http://dx.doi.org/10.1145/147508.147511.
- Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864-894, 1994. URL: http://dx.doi.org/10.1137/S0097539792225297.
- Paweł Gawrychowski and Adam Karczmarz. Improved bounds for shortest paths in dense distance graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1-61:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.61.
- Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, 1968. URL: http://dx.doi.org/10.1137/0116001.
- Dorothy M. Greig, Bruce T. Porteous, and Allan H. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society. Series B (Methodological), 51(2):271-279, 1989. URL: http://dx.doi.org/10.1111/j.2517-6161.1989.tb01764.x.
- David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, and Neal E. Young. Rounding algorithms for a geometric embedding of minimum multiway cut. Mathematics of Operations Research, 29(3):436-461, 2004. URL: http://dx.doi.org/10.1287/moor.1030.0086.
- Wolfgang Mulzer and Günter Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM, 55:Article 11, 29 pp., May 2008. URL: http://dx.doi.org/10.1145/1346330.1346336.