Approximating watchman routes

Joseph S.B. Mitchell

doi:10.1137/1.9781611973105.60

Approximating watchman routes

Joseph S.B. Mitchell

Applied Mathematics and Statistics

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

40 Scopus citations

Abstract

Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the "watchman") that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes. We present the first polynomial-time approximation algorithm for the watchman route problem in polygonal domains. Our algorithm has an approximation factor O(log² n). Further, we prove that the problem cannot be approximated in polynomial time to within a factor of c log n, for a constant c > 0, assuming that P≠NP.

Original language	English
Title of host publication	Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Publisher	Association for Computing Machinery
Pages	844-855
Number of pages	12
ISBN (Print)	9781611972511
DOIs	https://doi.org/10.1137/1.9781611973105.60
State	Published - 2013
Event	24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States Duration: Jan 6 2013 → Jan 8 2013

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/Territory	United States
City	New Orleans, LA
Period	01/6/13 → 01/8/13

Access to Document

10.1137/1.9781611973105.60

Cite this

@inproceedings{5c78c360be4d470d87bb24386e5ab65f,

title = "Approximating watchman routes",

abstract = "Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the {"}watchman{"}) that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes. We present the first polynomial-time approximation algorithm for the watchman route problem in polygonal domains. Our algorithm has an approximation factor O(log2 n). Further, we prove that the problem cannot be approximated in polynomial time to within a factor of c log n, for a constant c > 0, assuming that P≠NP.",

author = "Mitchell, \{Joseph S.B.\}",

year = "2013",

doi = "10.1137/1.9781611973105.60",

language = "English",

isbn = "9781611972511",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "844--855",

booktitle = "Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013",

note = "24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 ; Conference date: 06-01-2013 Through 08-01-2013",

}

Mitchell, JSB 2013, Approximating watchman routes. in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 844-855, 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, LA, United States, 01/6/13. https://doi.org/10.1137/1.9781611973105.60

TY - GEN

T1 - Approximating watchman routes

AU - Mitchell, Joseph S.B.

PY - 2013

Y1 - 2013

N2 - Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the "watchman") that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes. We present the first polynomial-time approximation algorithm for the watchman route problem in polygonal domains. Our algorithm has an approximation factor O(log2 n). Further, we prove that the problem cannot be approximated in polynomial time to within a factor of c log n, for a constant c > 0, assuming that P≠NP.

AB - Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the "watchman") that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes. We present the first polynomial-time approximation algorithm for the watchman route problem in polygonal domains. Our algorithm has an approximation factor O(log2 n). Further, we prove that the problem cannot be approximated in polynomial time to within a factor of c log n, for a constant c > 0, assuming that P≠NP.

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

U2 - 10.1137/1.9781611973105.60

DO - 10.1137/1.9781611973105.60

M3 - Conference contribution

AN - SCOPUS:84876045406

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 844

EP - 855

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -

Approximating watchman routes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this