×

Minimum-link watchman tours. (English) Zbl 1173.68757

Summary: We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of \(O(\log n)\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alsuwaiyel, M. H.; Lee, D. T., Minimal link visibility paths inside a simple polygon, Comput. Geom. Theory Appl., 3, 1, 1-25 (1993) · Zbl 0789.68138
[2] Alsuwaiyel, M. H.; Lee, D. T., Finding an approximate minimum-link visibility path inside a simple polygon, Inform. Process. Lett., 55, 2, 75-79 (1995) · Zbl 1022.68624
[3] Carlsson, S.; Jonsson, H.; Nilsson, B. J., Finding the shortest watchman route in a simple polygon, Discrete Comput. Geom., 22, 3, 377-402 (1999) · Zbl 0939.68136
[4] Chin, W.; Ntafos, S., Optimum watchman routes, Inform. Process. Lett., 28, 39-44 (1988) · Zbl 0652.68042
[5] Chin, W.-P; Ntafos, S., Shortest watchman routes in simple polygons, Discrete Comput. Geom., 6, 1, 9-31 (1991) · Zbl 0715.68037
[6] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538
[7] Ghosh, S. K.; Mount, D. M., An output-sensitive algorithm for computing visibility graphs, SIAM J. Comput., 20, 888-910 (1991) · Zbl 0768.68202
[8] Hammar, M.; Nilsson, B. J., Concerning the time bounds of existing shortest watchman route algorithms, (Proc. 11th International Symposium on Fundamentals of Computation Theory. Proc. 11th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 1279 (1997), Springer: Springer Berlin), 210-221 · Zbl 1507.68324
[9] Mata, C.; Mitchell, J. S.B, Approximation algorithms for geometric tour and network design problems, (Proc. 11th Annu. ACM Sympos. Comput. Geom. (1995)), 360-369
[10] Megiddo, N.; Tamir, A., On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 194-197 (1982) · Zbl 0507.90025
[11] B.J. Nilsson, Guarding art galleries—methods for mobile guards, PhD thesis, Lund University, 1995; B.J. Nilsson, Guarding art galleries—methods for mobile guards, PhD thesis, Lund University, 1995
[12] Tan, X., Fast computation of shortest watchman routes in simple polygons, Inform. Process. Lett., 77, 27-33 (2001) · Zbl 1003.68174
[13] Tan, X.; Hirata, T.; Inagaki, Y., Corrigendum to “An incremental algorithm for constructing shortest watchman routes”, Internat. J. Comput. Geom. Appl., 9, 3, 319-323 (1999) · Zbl 0959.68129
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.