liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Computing Nonsimple Polygons of Minimum Perimeter
TU Braunschweig, Germany.
TU Braunschweig, Germany.
TU Braunschweig, Germany.
Swiss Federal Institute Technology, Switzerland.
Show others and affiliations
2016 (English)In: EXPERIMENTAL ALGORITHMS, SEA 2016, SPRINGER INT PUBLISHING AG , 2016, Vol. 9685, 134-149 p.Conference paper (Refereed)
Abstract [en]

We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. 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 MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of 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 additional 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 using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.

Place, publisher, year, edition, pages
SPRINGER INT PUBLISHING AG , 2016. Vol. 9685, 134-149 p.
Lecture Notes in Computer Science, ISSN 0302-9743
Keyword [en]
Traveling Salesman Problem (TSP); Minimum Perimeter Polygon (MPP); Curve reconstruction; NP-hardness; Exact optimization; Integer programming; Computational geometry meets combinatorial optimization
National Category
Discrete Mathematics
URN: urn:nbn:se:liu:diva-132697DOI: 10.1007/978-3-319-38851-9_10ISI: 000386324300010ISBN: 978-3-319-38850-2; 978-3-319-38851-9 OAI: diva2:1048099
15th International Symposium on Experimental Algorithms (SEA)
Available from: 2016-11-20 Created: 2016-11-18 Last updated: 2016-11-20

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Schmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 6 hits
ReferencesLink to record
Permanent link

Direct link