## 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
### 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`(`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/(3`k`))-approximation
algorithm.

Last update: October 12, 2020.