Computing nonsimple polygons of minimum perimeter

S.P. Fekete, A. Haas, M. Hemmer, M. Hoffmann, I. Kostitsyna, D. Krupke, F. Maurer, J.S.B. Mitchell, A. Schmidt, C. Schmidt, J. Troegel

Research output: Contribution to journalArticleAcademicpeer-review

90 Downloads (Pure)

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.



Original languageEnglish
Pages (from-to)340-365
Number of pages26
JournalJournal of Computational Geometry
Volume8
Issue number1
DOIs
Publication statusPublished - 2018

Fingerprint

Traveling salesman problem
Perimeter
Travelling salesman problems
Polygon
Computing
Curve Reconstruction
Cycle Cover
Benchmark
Simple Polygon
NP-hardness
Delaunay triangulation
Integer programming
Topological Structure
Approximation algorithms
Triangulation
Integer Programming
Set theory
Combinatorics
Approximation Algorithms
Optimal Solution

Cite this

Fekete, S. P., Haas, A., Hemmer, M., Hoffmann, M., Kostitsyna, I., Krupke, D., ... Troegel, J. (2018). Computing nonsimple polygons of minimum perimeter. Journal of Computational Geometry, 8(1), 340-365. https://doi.org/10.20382/jocg.v8i1a13
Fekete, S.P. ; Haas, A. ; Hemmer, M. ; Hoffmann, M. ; Kostitsyna, I. ; Krupke, D. ; Maurer, F. ; Mitchell, J.S.B. ; Schmidt, A. ; Schmidt, C. ; Troegel, J. / Computing nonsimple polygons of minimum perimeter. In: Journal of Computational Geometry. 2018 ; Vol. 8, No. 1. pp. 340-365.
@article{788095af337d49cf9c42b595bd4f5dcf,
title = "Computing nonsimple polygons of minimum perimeter",
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.",
author = "S.P. Fekete and A. Haas and M. Hemmer and M. Hoffmann and I. Kostitsyna and D. Krupke and F. Maurer and J.S.B. Mitchell and A. Schmidt and C. Schmidt and J. Troegel",
year = "2018",
doi = "10.20382/jocg.v8i1a13",
language = "English",
volume = "8",
pages = "340--365",
journal = "Journal of Computational Geometry",
issn = "1920-180X",
publisher = "Macodrum library, Carleton University",
number = "1",

}

Fekete, SP, Haas, A, Hemmer, M, Hoffmann, M, Kostitsyna, I, Krupke, D, Maurer, F, Mitchell, JSB, Schmidt, A, Schmidt, C & Troegel, J 2018, 'Computing nonsimple polygons of minimum perimeter', Journal of Computational Geometry, vol. 8, no. 1, pp. 340-365. https://doi.org/10.20382/jocg.v8i1a13

Computing nonsimple polygons of minimum perimeter. / Fekete, S.P.; Haas, A.; Hemmer, M.; Hoffmann, M.; Kostitsyna, I.; Krupke, D.; Maurer, F.; Mitchell, J.S.B.; Schmidt, A.; Schmidt, C.; Troegel, J.

In: Journal of Computational Geometry, Vol. 8, No. 1, 2018, p. 340-365.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Computing nonsimple polygons of minimum perimeter

AU - Fekete, S.P.

AU - Haas, A.

AU - Hemmer, M.

AU - Hoffmann, M.

AU - Kostitsyna, I.

AU - Krupke, D.

AU - Maurer, F.

AU - Mitchell, J.S.B.

AU - Schmidt, A.

AU - Schmidt, C.

AU - Troegel, J.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

U2 - 10.20382/jocg.v8i1a13

DO - 10.20382/jocg.v8i1a13

M3 - Article

VL - 8

SP - 340

EP - 365

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

SN - 1920-180X

IS - 1

ER -