Geometric multicut

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

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.
OriginalsprogEngelsk
Titel46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
RedaktørerChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
Antal sider15
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2019
Artikelnummer9
ISBN (Elektronisk)9783959771092
DOI
StatusUdgivet - 2019
Begivenhed46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Grækenland
Varighed: 9 jul. 201912 jul. 2019

Konference

Konference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
LandGrækenland
ByPatras
Periode09/07/201912/07/2019
SponsorCenter for Perspicuous Computing (CPEC), University of Patras
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind132
ISSN1868-8969

ID: 231752405