@inproceedings{be1488e1bca14164853e48276b947204,
title = "Geometric multicut",
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(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.",
keywords = "Clustering, Multicut, Steiner tree",
author = "Mikkel Abrahamsen and Panos Giannopoulos and Maarten L{\"o}ffler and G{\"u}nter Rote",
year = "2019",
doi = "10.4230/LIPIcs.ICALP.2019.9",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",
booktitle = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019",
note = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 ; Conference date: 09-07-2019 Through 12-07-2019",
}