City Research Online

Geometric Multicut

Giannopoulos, P. ORCID: 0000-0002-6261-1961, Abrahamsen, M., Löffler, M. and Rote, G. (2019). Geometric Multicut. Paper presented at the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 8 - 12 July 2019, Patras, Greece.

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

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote; licensed under Creative Commons License CC-BY 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Editors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi; Article No. 4; pp. 4:1–4:13
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/22319
[img]
Preview
Text - Published Version
Available under License Creative Commons Attribution.

Download (644kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login