Geometric multicut
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- OA-Geometric Multicut
Forlagets udgivne version, 627 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 |
Redaktører | Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi |
Antal sider | 15 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2019 |
Artikelnummer | 9 |
ISBN (Elektronisk) | 9783959771092 |
DOI | |
Status | Udgivet - 2019 |
Begivenhed | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Grækenland Varighed: 9 jul. 2019 → 12 jul. 2019 |
Konference
Konference | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 |
---|---|
Land | Grækenland |
By | Patras |
Periode | 09/07/2019 → 12/07/2019 |
Sponsor | Center for Perspicuous Computing (CPEC), University of Patras |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 132 |
ISSN | 1868-8969 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 231752405