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

doi:10.1007/978-3-319-38851-9_10

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

1 Citaat (Scopus)

351 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Proc. 15th International Symposium on Experimental Algorithms (SEA)
Redacteuren	Andrew V. Goldberg, Alexander S. Kulikov
Plaats van productie	Dordrecht
Uitgeverij	Springer
Pagina's	134-149
Aantal pagina's	16
ISBN van elektronische versie	978-3-319-38851-9
ISBN van geprinte versie	978-3-319-38851-9
DOI's	https://doi.org/10.1007/978-3-319-38851-9_10
Status	Gepubliceerd - 2016
Evenement	International Symposium on Experimental Algorithms: 15th International Symposium - St. Petersburg, Rusland Duur: 5 jun 2016 → 8 jun 2016 http://link.springer.com/book/10.1007/978-3-319-38851-9

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	9685

Congres

Congres	International Symposium on Experimental Algorithms
Verkorte titel	SEA 2016
Land/Regio	Rusland
Stad	St. Petersburg
Periode	5/06/16 → 8/06/16
Internet adres	http://link.springer.com/book/10.1007/978-3-319-38851-9

Toegang tot document

10.1007/978-3-319-38851-9_10

submissionFinale auteursversie , 1,64 MB

Citeer dit

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. (2016). Computing nonsimple polygons of minimum perimeter. In A. V. Goldberg, & A. S. Kulikov (editors), Proc. 15th International Symposium on Experimental Algorithms (SEA) (blz. 134-149). (Lecture Notes in Computer Science; Vol. 9685). Springer. https://doi.org/10.1007/978-3-319-38851-9_10

@inproceedings{155f9f0bf7a14f38b5905b04d345ffc2,

title = "Computing nonsimple polygons of minimum perimeter",

abstract = "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.",

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 = "2016",

doi = "10.1007/978-3-319-38851-9\_10",

language = "English",

isbn = "978-3-319-38851-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "134--149",

editor = "Goldberg, \{Andrew V.\} and Kulikov, \{Alexander S.\}",

booktitle = "Proc. 15th International Symposium on Experimental Algorithms (SEA)",

address = "Germany",

note = "International Symposium on Experimental Algorithms : 15th International Symposium, SEA 2016 ; Conference date: 05-06-2016 Through 08-06-2016",

url = "http://link.springer.com/book/10.1007/978-3-319-38851-9",

}

Fekete, SP, Haas, A, Hemmer, M, Hoffmann, M, Kostitsyna, I, Krupke, D, Maurer, F, Mitchell, JSB, Schmidt, A, Schmidt, C & Troegel, J 2016, Computing nonsimple polygons of minimum perimeter. in AV Goldberg & AS Kulikov (reds.), Proc. 15th International Symposium on Experimental Algorithms (SEA). Lecture Notes in Computer Science, vol. 9685, Springer, Dordrecht, blz. 134-149, International Symposium on Experimental Algorithms, St. Petersburg, Rusland, 5/06/16. https://doi.org/10.1007/978-3-319-38851-9_10

Computing nonsimple polygons of minimum perimeter. / Fekete, S.P.; Haas, A.; Hemmer, M. et al.
Proc. 15th International Symposium on Experimental Algorithms (SEA). reds. / Andrew V. Goldberg; Alexander S. Kulikov. Dordrecht: Springer, 2016. blz. 134-149 (Lecture Notes in Computer Science; Vol. 9685).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

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 - 2016

Y1 - 2016

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

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

U2 - 10.1007/978-3-319-38851-9_10

DO - 10.1007/978-3-319-38851-9_10

M3 - Conference contribution

SN - 978-3-319-38851-9

T3 - Lecture Notes in Computer Science

SP - 134

EP - 149

BT - Proc. 15th International Symposium on Experimental Algorithms (SEA)

A2 - Goldberg, Andrew V.

A2 - Kulikov, Alexander S.

PB - Springer

CY - Dordrecht

T2 - International Symposium on Experimental Algorithms

Y2 - 5 June 2016 through 8 June 2016

ER -

Computing nonsimple polygons of minimum perimeter

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit