Approximation algorithms for the watchman route and zookeeper's problems

Alsuwaiyel, 1995, Finding an approximate minimum-link visibility path inside a simple polygon, Inform. Process. Lett., 55, 75, 10.1016/0020-0190(95)00072-K

S. Bespamyatnikh, An O(nlogn) algorithm for the zookeeper's problem, in: Comput. Geom. Theory Appl. 24 (2002) 63–74.

S. Carlsson, H. Jonsson, B.J. Nilsson, Approximating the shortest watchman route in a simple polygon, Technical Report, Department of Computer Science, Lund University, Sweden, 1997.

Chazelle, 1991, Triangulating a simple polygon in linear time, Discrete Comput. Geom., 6, 485, 10.1007/BF02574703

Chazelle, 1989, Visibility and intersection problem in plane geometry, Discrete Comput. Geom., 4, 551, 10.1007/BF02187747

Chin, 1988, Optimum watchman routes, Inform. Process. Lett., 28, 39, 10.1016/0020-0190(88)90141-X

Chin, 1992, The zookeeper route problem, Inform. Sci., 63, 245, 10.1016/0020-0255(92)90072-G

Das, 1997, LR-visibility in polygons, Comput. Geom. Theory Appl., 7, 37, 10.1016/0925-7721(95)00042-9

Guibas, 1987, Linear time algorithms for visibility and shortest path problems inside simple triangulated polygons, Algorithmica, 2, 209, 10.1007/BF01840360

Hershberger, 1989, Finding the visibility graph of a simple polygon in time proportional to its size, Algorithmica, 4, 141, 10.1007/BF01553883

J. Hershberger, J. Snoeyink, An efficient solution to the zookeeper's problem, Proceedings of the Sixth Canadian Conference on Computational Geometry, Saskatoon, SK, Canada 1994, pp. 104–109.

J. Hershberger, S. Suri, Practical methods for approximating shortest paths on a convex polytope in R3, in: Comput. Geom. Theory Appl. 10 (1998) 31–46.

H. Jonsson, On the zookeeper's problem, in: An approximative solution to the zookeeper's problems, to appear in Inform. Process. Lett.

C. Mata, J.S.B. Mitchell, Approximation algorithms for geometric tour and network design problems, in: Proceedings of the 11th Annual ACM Symposium on Computational Geometry, Vancouver, BC, Canada 1995, pp. 360–369.

B. Nilsson, Guarding art galleries; Methods for mobile guards, Ph.D. Thesis, Lund University, Sweden, 1995.

Tan, 2001, Shortest zookeeper's routes in simple polygons, Inform. Process. Lett., 77, 23, 10.1016/S0020-0190(00)00144-7

Tan, 2001, Fast computation of shortest watchman routes in simple polygons, Inform. Process. Lett., 77, 27, 10.1016/S0020-0190(00)00146-0

Tan, 1993, An incremental algorithm for constructing shortest watchman routes, Internat. J. Comput. Geom. Appl., 3, 351, 10.1142/S0218195993000233

Tan, 1999, Corrigendum to an incremental algorithm for constructing shortest watchman routes, Internat. J. Comput. Geom. Appl., 9, 319, 10.1142/S0218195999000212