Back to Search
Start Over
Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane
- Source :
- 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
- Publication Year :
- 2020
- Publisher :
- Springer Science and Business Media LLC, 2020.
-
Abstract
- We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent 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 ifFcontains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem asgeometrick-cut, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an$$O(n^4\log ^3\!n)$$O(n4log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours withncorners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised$$4/3\cdot 1.2965$$4/3·1.2965-approximation algorithm for polygons and any number of colours.
- Subjects :
- QA75
geometry
0102 computer and information sciences
02 engineering and technology
Disjoint sets
01 natural sciences
Fence (mathematics)
Theoretical Computer Science
Combinatorics
symbols.namesake
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
study
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung
Informatik
QA
Mathematics
Separation problem
Plane (geometry)
Approximation algorithm
16. Peace & justice
Object (computer science)
separation problem
Jordan curve theorem
Computational Theory and Mathematics
010201 computation theory & mathematics
symbols
020201 artificial intelligence & image processing
Geometry and Topology
Subjects
Details
- ISSN :
- 14320444 and 01795376
- Volume :
- 64
- Database :
- OpenAIRE
- Journal :
- Discrete & Computational Geometry
- Accession number :
- edsair.doi.dedup.....33e146a6c303211ed2f8d156ffa90ece