City Research Online

Geometric Multicut

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

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 Science & Technology > Computer Science
School of Science & Technology > Computer Science > giCentre
[thumbnail of geometric-multisep.pdf]
Preview
Text - Published Version
Available under License Creative Commons Attribution.

Download (644kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login