TSP in a Simple Polygon

Henk Alkema; Mark de Berg; Morteza Monemizadeh; Leonidas Theocharous

doi:10.4230/LIPIcs.ESA.2022.5

TSP in a Simple Polygon

Henk Alkema
, Mark de Berg
, Morteza Monemizadeh
, Leonidas Theocharous

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

20 Downloads (Pure)

Abstract

We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2O(√ n log n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.

Original language	English
Title of host publication	30th Annual European Symposium on Algorithms, ESA 2022
Editors	Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	5:1-5:14
Number of pages	14
ISBN (Electronic)	978-3-95977-247-1
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2022.5
Publication status	Published - 1 Sept 2022
Event	30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, Germany Duration: 5 Sept 2022 → 9 Sept 2022

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	244
ISSN (Print)	1868-8969

Conference

Conference	30th Annual European Symposium on Algorithms, ESA 2022
Country/Territory	Germany
City	Berlin/Potsdam
Period	5/09/22 → 9/09/22

Keywords

Subexponential algorithms
TSP with obstacles
Traveling Salesman Problem

Access to Document

10.4230/LIPIcs.ESA.2022.5

pdfFinal published version, 946 KBLicence: CC BY

Cite this

Alkema, H., Berg, M. D., Monemizadeh, M., & Theocharous, L. (2022). TSP in a Simple Polygon. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms, ESA 2022 (pp. 5:1-5:14). Article 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 244). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.5

@inproceedings{b142044e3414498f89adf9b6791c6622,

title = "TSP in a Simple Polygon",

abstract = "We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2O(√ n log n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.",

keywords = "Subexponential algorithms, TSP with obstacles, Traveling Salesman Problem",

author = "Henk Alkema and Berg, \{Mark de\} and Morteza Monemizadeh and Leonidas Theocharous",

year = "2022",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2022.5",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "5:1--5:14",

editor = "Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman",

booktitle = "30th Annual European Symposium on Algorithms, ESA 2022",

note = "30th Annual European Symposium on Algorithms, ESA 2022 ; Conference date: 05-09-2022 Through 09-09-2022",

}

Alkema, H, Berg, MD , Monemizadeh, M & Theocharous, L 2022, TSP in a Simple Polygon. in S Chechik, G Navarro, E Rotenberg & G Herman (eds), 30th Annual European Symposium on Algorithms, ESA 2022., 5, Leibniz International Proceedings in Informatics, LIPIcs, vol. 244, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 5:1-5:14, 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, 5/09/22. https://doi.org/10.4230/LIPIcs.ESA.2022.5

TSP in a Simple Polygon. / Alkema, Henk; Berg, Mark de ; Monemizadeh, Morteza et al.
30th Annual European Symposium on Algorithms, ESA 2022. ed. / Shiri Chechik; Gonzalo Navarro; Eva Rotenberg; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. p. 5:1-5:14 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 244).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - TSP in a Simple Polygon

AU - Alkema, Henk

AU - Berg, Mark de

AU - Monemizadeh, Morteza

AU - Theocharous, Leonidas

PY - 2022/9/1

Y1 - 2022/9/1

N2 - We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2O(√ n log n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.

AB - We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2O(√ n log n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.

KW - Subexponential algorithms

KW - TSP with obstacles

KW - Traveling Salesman Problem

UR - https://www.scopus.com/pages/publications/85137590581

U2 - 10.4230/LIPIcs.ESA.2022.5

DO - 10.4230/LIPIcs.ESA.2022.5

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 5:1-5:14

BT - 30th Annual European Symposium on Algorithms, ESA 2022

A2 - Chechik, Shiri

A2 - Navarro, Gonzalo

A2 - Rotenberg, Eva

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 30th Annual European Symposium on Algorithms, ESA 2022

Y2 - 5 September 2022 through 9 September 2022

ER -

TSP in a Simple Polygon

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this