Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane

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.

keywords: Computational Geometry

Journal Article (peer-reviewed)

Günter Rote, Maarten Löffler, Mikkel Abrahamsen, Panos Giannopoulos
Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane
Discrete & Computational Geometry
64, 575–607, 2020
https://doi.org/10.1007/s00454-020-00232-w

Conference Proceedings (peer-reviewed)

Günter Rote, Maarten Löffler, Mikkel Abrahamsen, Panos Giannopoulos
Geometric Multicut
Proc. International Conference on Algorithms, Languages and Programming
9:1–9:15, 2019
http://drops.dagstuhl.de/opus/volltexte/2019/10585

back to list