TY - JOUR
T1 - Geometric Multicut
T2 - Shortest Fences for Separating Groups of Objects in the Plane
AU - Abrahamsen, Mikkel
AU - Giannopoulos, Panos
AU - Löffler, Maarten
AU - Rote, Günter
PY - 2020
Y1 - 2020
N2 - We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane with k different colours, compute a shortest “fence” F, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. 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, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an O(n4log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours with n corners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised 4/3⋅1.2965-approximation algorithm for polygons and any number of colours.
AB - We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane with k different colours, compute a shortest “fence” F, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. 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, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an O(n4log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours with n corners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised 4/3⋅1.2965-approximation algorithm for polygons and any number of colours.
U2 - 10.1007/s00454-020-00232-w
DO - 10.1007/s00454-020-00232-w
M3 - Journal article
VL - 64
SP - 575
EP - 607
JO - Discrete & Computational Geometry
JF - Discrete & Computational Geometry
SN - 0179-5376
ER -