Abstract
In this paper we present an O(n 4, log logn) algorithm to find a shortest watchman route in a simple polygon through a point,s, in its boundary. A watchman route is a route such that each point in the interior of the polygon is visible from at least one point along the route.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
[CN] W. P. Chin and S. Ntafos, Optimum watchman routes,Inform. Process. Lett. 28 (1988), 39–44; preliminary version inProceedings of the 2nd ACM Symposium on Computational Geometry, pp. 24–33, 1986.
[GH*] L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons,Proceedings of the ACM Symposium on Computational Geometry, pp. 1–13, 1986.
[O] J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford, 1987.
[S] S. Suri, Minimum Link Paths in Polygons and Related Problems, Ph.D. Dissertation, John Hopkins University, 1987.
[TV] R.E. Tarjan and C. Van Wyk, An O(n log logn) algorithm for triangulating a simple polygon,SIAM J. Comput. 17 (1988), 143–178.
Author information
Authors and Affiliations
Additional information
S. Ntafos was supported in part by a grant from Texas Instruments, Inc.
Rights and permissions
About this article
Cite this article
Chin, WP., Ntafos, S. Shortest watchman routes in simple polygons. Discrete Comput Geom 6, 9–31 (1991). https://doi.org/10.1007/BF02574671
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574671