Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote:

1. Geometric multicut

In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, July 2019. Editors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi. Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019, Vol. 132, pp. 9:1–9:15. doi:10.4230/LIPIcs.ICALP.2019.9, arXiv:1902.04045 [cs.CG].  →BibTeX

2. Geometric multicut: shortest fences for separating groups of objects in the plane

Discrete & Computational Geometry 64 (2020), 575–607, doi:10.1007/s00454-020-00232-w.  →BibTeX


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 log3n)-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.

  pdf file
other papers about this subject
Last update: October 12, 2020.