Computing nonsimple polygons of minimum perimeter
OPEN ACCESS
Loading...
Author / Producer
Date
2017
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
8 (1)
Pages / Article No.
340 - 365
Publisher
Carleton University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)