by Li, F and Klette, R
Abstract:
So far, the best result in running time for solving the fixed watchman route problem (i.e., shortest path for viewing any point in a simple polygon with given start point) is O(n3 log n), published in 2003 by M. Dror, A. Efrat, A. Lubiw, and J. Mitchell. – This paper provides an algorithm with κ(ε) · O(kn) runtime, where n is the number of vertices of the given simple polygon Π, and k the number of essential cuts; κ(ε) defines the numerical accuracy in dependency of a selected constant ε > 0. Moreover, our algorithm is significantly simpler, easier to understand and implement than previous ones for solving the fixed watchman route problem.
Reference:
Watchman route in a simple polygon with a rubberband algorithm (Li, F and Klette, R), In Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010, 2010.
Bibtex Entry:
@inproceedings{li2010watchmanalgorithm,
author = "Li, F and Klette, R",
booktitle = "Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010",
pages = "1--4",
title = "Watchman route in a simple polygon with a rubberband algorithm",
year = "2010",
abstract = "So far, the best result in running time for solving the fixed watchman route problem (i.e., shortest path for viewing any point in a simple polygon with given start point) is O(n3 log n), published in 2003 by M. Dror, A. Efrat, A. Lubiw, and J. Mitchell. - This paper provides an algorithm with κ(ε) · O(kn) runtime, where n is the number of vertices of the given simple polygon Π, and k the number of essential cuts; κ(ε) defines the numerical accuracy in dependency of a selected constant ε > 0. Moreover, our algorithm is significantly simpler, easier to understand and implement than previous ones for solving the fixed watchman route problem.",
language = "eng",
}