Standard
Geometric multicut. / Abrahamsen, Mikkel; Giannopoulos, Panos; Löffler, Maarten; Rote, Günter.
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. ed. / Christel Baier; Ioannis Chatzigiannakis; Paola Flocchini; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 9 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Abrahamsen, M, Giannopoulos, P, Löffler, M & Rote, G 2019,
Geometric multicut. in C Baier, I Chatzigiannakis, P Flocchini & S Leonardi (eds),
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019., 9, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 132, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece,
09/07/2019.
https://doi.org/10.4230/LIPIcs.ICALP.2019.9
APA
Abrahamsen, M., Giannopoulos, P., Löffler, M., & Rote, G. (2019).
Geometric multicut. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.),
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [9] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 132
https://doi.org/10.4230/LIPIcs.ICALP.2019.9
Vancouver
Abrahamsen M, Giannopoulos P, Löffler M, Rote G.
Geometric multicut. In Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 9. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132).
https://doi.org/10.4230/LIPIcs.ICALP.2019.9
Author
Abrahamsen, Mikkel ; Giannopoulos, Panos ; Löffler, Maarten ; Rote, Günter. / Geometric multicut. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. editor / Christel Baier ; Ioannis Chatzigiannakis ; Paola Flocchini ; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132).
Bibtex
@inproceedings{be1488e1bca14164853e48276b947204,
title = "Geometric multicut",
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(n4 log3 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.",
keywords = "Clustering, Multicut, Steiner tree",
author = "Mikkel Abrahamsen and Panos Giannopoulos and Maarten L{\"o}ffler and G{\"u}nter Rote",
year = "2019",
doi = "10.4230/LIPIcs.ICALP.2019.9",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",
booktitle = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019",
note = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 ; Conference date: 09-07-2019 Through 12-07-2019",
}
RIS
TY - GEN
T1 - Geometric multicut
AU - Abrahamsen, Mikkel
AU - Giannopoulos, Panos
AU - Löffler, Maarten
AU - Rote, Günter
PY - 2019
Y1 - 2019
N2 - 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(n4 log3 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.
AB - 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(n4 log3 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.
KW - Clustering
KW - Multicut
KW - Steiner tree
UR - http://www.scopus.com/inward/record.url?scp=85069197288&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2019.9
DO - 10.4230/LIPIcs.ICALP.2019.9
M3 - Article in proceedings
AN - SCOPUS:85069197288
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
A2 - Baier, Christel
A2 - Chatzigiannakis, Ioannis
A2 - Flocchini, Paola
A2 - Leonardi, Stefano
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Y2 - 9 July 2019 through 12 July 2019
ER -
