Geometric multicut
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- OA-Geometric Multicut
Final published version, 627 KB, PDF document
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(n4 log3 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.
Original language | English |
---|---|
Title of host publication | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 |
Editors | Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi |
Number of pages | 15 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2019 |
Article number | 9 |
ISBN (Electronic) | 9783959771092 |
DOIs | |
Publication status | Published - 2019 |
Event | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece Duration: 9 Jul 2019 → 12 Jul 2019 |
Conference
Conference | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 |
---|---|
Land | Greece |
By | Patras |
Periode | 09/07/2019 → 12/07/2019 |
Sponsor | Center for Perspicuous Computing (CPEC), University of Patras |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 132 |
ISSN | 1868-8969 |
- Clustering, Multicut, Steiner tree
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
ID: 231752405