2026-08-06T02:51:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10585 2024-03-06T10:46:12Z ddc:004 open_access

Geometric Multicut Abrahamsen, Mikkel Giannopoulos, Panos Löffler, Maarten Rote, Günter multicut clustering Steiner tree 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(n^4 log^3 n)-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen and Panos Giannopoulos and Maarten Löffler and Günter Rote 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.9 urn:nbn:de:0030-drops-105850 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.9 eng https://creativecommons.org/licenses/by/3.0/legalcode