Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Geometric Multicut : Shortest Fences for Separating Groups of Objects in the Plane. / Abrahamsen, Mikkel; Giannopoulos, Panos; Löffler, Maarten; Rote, Günter.

In: Discrete & Computational Geometry, Vol. 64, 2020, p. 575–607.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Abrahamsen, M, Giannopoulos, P, Löffler, M & Rote, G 2020, 'Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane', Discrete & Computational Geometry, vol. 64, pp. 575–607. https://doi.org/10.1007/s00454-020-00232-w

APA

Abrahamsen, M., Giannopoulos, P., Löffler, M., & Rote, G. (2020). Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane. Discrete & Computational Geometry, 64, 575–607. https://doi.org/10.1007/s00454-020-00232-w

Vancouver

Abrahamsen M, Giannopoulos P, Löffler M, Rote G. Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane. Discrete & Computational Geometry. 2020;64:575–607. https://doi.org/10.1007/s00454-020-00232-w

Author

Abrahamsen, Mikkel ; Giannopoulos, Panos ; Löffler, Maarten ; Rote, Günter. / Geometric Multicut : Shortest Fences for Separating Groups of Objects in the Plane. In: Discrete & Computational Geometry. 2020 ; Vol. 64. pp. 575–607.

Bibtex

@article{a72cc365a8db4f60b6fc950295d99fac,
title = "Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane",
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(n4log3n)-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.",
author = "Mikkel Abrahamsen and Panos Giannopoulos and Maarten L{\"o}ffler and G{\"u}nter Rote",
year = "2020",
doi = "10.1007/s00454-020-00232-w",
language = "English",
volume = "64",
pages = "575–607",
journal = "Discrete & Computational Geometry",
issn = "0179-5376",
publisher = "Springer",

}

RIS

TY - JOUR

T1 - Geometric Multicut

T2 - Shortest Fences for Separating Groups of Objects in the Plane

AU - Abrahamsen, Mikkel

AU - Giannopoulos, Panos

AU - Löffler, Maarten

AU - Rote, Günter

PY - 2020

Y1 - 2020

N2 - 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(n4log3n)-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.

AB - 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(n4log3n)-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.

U2 - 10.1007/s00454-020-00232-w

DO - 10.1007/s00454-020-00232-w

M3 - Journal article

VL - 64

SP - 575

EP - 607

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

SN - 0179-5376

ER -

ID: 246865510