Search: WFRF:(Krupke Dominik) >
Computing Nonsimple...
Computing Nonsimple Polygons of Minimum Perimeter
-
- Fekete, Sándor P. (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, Germany
-
- Haas, Andreas (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, Germany
-
- Hemmer, Michael (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, Germany
-
show more...
-
- Hoffmann, Michael (author)
- Department of Computer Science, ETH Zürich, Zürich, Switzerland
-
- Kostitsyna, Irina (author)
- Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands
-
- Krupke, Dominik (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, GermanyDepartment of Computer Science, TU Braunschweig, Braunschweig, Germany
-
- Maurer, Florian (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, Germany
-
- Mitchell, Joseph S.B. (author)
- Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA
-
- Schmidt, Arne (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, Germany
-
- Schmidt, Christiane (author)
- Linköpings universitet,Kommunikations- och transportsystem,Tekniska fakulteten
-
- Troegel, Julian (author)
- Department of Computer Science, TU Braunschweig, Braunschweig, Germany
-
show less...
-
(creator_code:org_t)
- Ottawa, Canada : Carleton University * Department of Mathematics and Statistics, 2017
- 2017
- English.
-
In: Journal of Computational Geometry. - Ottawa, Canada : Carleton University * Department of Mathematics and Statistics. - 1920-180X. ; 8:1
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.2...
-
show less...
Abstract
Subject headings
Close
- We consider the Minimum Perimeter Polygon Problem (MP3): for a given set V of points in the plane, find a polygon P with holes that has vertex set V , such that the total boundary length is smallest possible. The MP3 can be considered a natural geometric generalization of the Traveling Salesman Problem (TSP), which asks for a simple polygon with minimum perimeter. Just like the TSP, the MP3 occurs naturally in the context of curve reconstruction. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MP3. On the positive side, we provide constant-factor approximation algorithms. In addition to algorithms with theoretical worst-case guarantess, we provide practical methods for computing provably optimal solutions for relatively large instances, based on integer programming. An additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that restricting the set of connections between points to edges of the Delaunay triangulation yields results that are on average within 0.5% of the optimum for large classes of benchmark instances.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database
- By the author/editor
-
Fekete, Sándor P ...
-
Haas, Andreas
-
Hemmer, Michael
-
Hoffmann, Michae ...
-
Kostitsyna, Irin ...
-
Krupke, Dominik
-
show more...
-
Maurer, Florian
-
Mitchell, Joseph ...
-
Schmidt, Arne
-
Schmidt, Christi ...
-
Troegel, Julian
-
show less...
- About the subject
-
- NATURAL SCIENCES
-
NATURAL SCIENCES
-
and Computer and Inf ...
-
and Computer Science ...
- Articles in the publication
-
Journal of Compu ...
- By the university
-
Linköping University