Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane
- PDF / 2,036,274 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 105 Downloads / 188 Views
Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane Mikkel Abrahamsen1 · Panos Giannopoulos2 · Maarten Löffler3 · Günter Rote4 Received: 7 May 2019 / Revised: 3 March 2020 / Accepted: 3 July 2020 © The Author(s) 2020
Abstract 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(n 4 log3 n)-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.
1 Introduction Problem Statement We are given k pairwise interior-disjoint sets B1 , B2 , . . . , Bk in the plane, not necessarily connected. We want to find a covering of the plane R2 = B¯ 1 ∪ B¯ 2 ∪ · · · ∪ B¯ k such that the sets B¯ i are k closed and interior-disjoint, ∂ B¯ i between the different Bi ⊆ B¯ i , and the total length of the boundary F = i=1 sets B¯ i is minimized.
Dedicated to the memory of Ricky Pollack Editor in Charge: János Pach. An extended abstract of this work has been presented at the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) in July 2019 in Patras, Greece [2]. M. Abrahamsen: Supported by the Innovation Fund Denmark through the DABAI project. BARC is supported by the VILLUM Foundation grant 16582. M. Löffler: Partially supported by the Netherlands Organisation for Scientific Research (NWO); 614.001.504. Extended author information available on the last page of the article
123
Discrete & Computational Geometry
We think of the k sets Bi as having k different colours and each set Bi as a union of simple geometric objects like circular disks or simple polygons. We call B¯ i the territory of colour i. Examples are shown in Figs. 1 and 2. The “fence” F consists of the boundaries that separate the territories, or alternatively, F is the set of points belonging to more than one territory. As we can see, the fence does not have to be connected, and a territory can have more than one connected component. An alternative view of the problem concentrates on the fence: A fence is defined as a union of curves F such that each connected component of R2 \ F intersects at most one set Bi . An interior-disjoint covering as defined above gives, by definition, such a fence. Likewise, a fence F induces such a covering, by assigning each connected
Fig. 1 An instance with k = 2 sets, red and green, with two disks each; the big green disk is only partially shown
Data Loading...
