Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane
Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote · Discrete & Computational Geometry · 2020
Abstract We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent 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 ifFcontains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem asgeometrick-cut, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an $$O(n^4\log ^3\!n)$$ O(n4log3n) -time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours withncorners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised $$4/3\cdot 1.2965$$ 4/3·1.2965 -approximation algorithm for polygons and any number of colours.