×

Watchman routes for lines and line segments. (English) Zbl 1302.90174

Summary: Given a set \(\mathcal L\) of non-parallel lines in the plane, a watchman route (tour) for \(\mathcal L\) is a closed curve contained in the union of the lines in \(\mathcal L\) such that every line is visited (intersected) by the route; we similarly define a watchman route (tour) for a connected set \(\mathcal S\) of line segments. The watchman route problem for a given set of lines or line segments is to find a shortest watchman route for the input set, and these problems are natural special cases of the watchman route problem in a polygon with holes (a polygonal domain).{ }In this paper, we show that the problem of computing a shortest watchman route for a set of \(n\) non-parallel lines in the plane is polynomially tractable, while it becomes NP-hard in 3D. We give an alternative NP-hardness proof of this problem for line segments in the plane and obtain a polynomial-time approximation algorithm with ratio \(O(\log^3n)\). Additionally, we consider some special cases of the watchman route problem on line segments, for which we provide exact algorithms or improved approximations.

MSC:

90C27 Combinatorial optimization
90C39 Dynamic programming
65K05 Numerical mathematical programming methods
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W20 Randomized algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abellanas, M.; Bajuelos, A.; Matos, I., Maximum covered path within a region, (Proc. 13th Encuentros de Geometría Computacional (2009)), 277-284
[2] Ballinger, B.; Benbernou, N.; Bose, P.; Damian, M.; Demaine, E. D.; Dujmović, V.; Flatland, R.; Hurtado, F.; Iacono, J.; Lubiw, A.; Morin, P.; Sacristán, V.; Souvaine, D.; Uehara, R., Coverage with \(k\)-transmitters in the presence of obstacles, (Proc. 4th Annual International Conference on Combinatorial Optimization and Applications. Proc. 4th Annual International Conference on Combinatorial Optimization and Applications, Lect. Notes Comput. Sci., vol. 6509 (2010), Springer), 1-15 · Zbl 1311.90116
[3] Bern, M.; Plassmann, P., The Steiner problem with edge lengths 1 and 2, Inf. Process. Lett., 32, 4, 171-176 (1989) · Zbl 0677.68074
[4] Brimkov, V. E.; Leach, A.; Mastroianni, M.; Wu, J., Guarding a set of line segments in the plane, Theor. Comput. Sci., 412, 15, 1313-1324 (2011) · Zbl 1207.68414
[5] Carlsson, S.; Jonsson, H., Computing a shortest watchman path in a simple polygon in polynomial-time, (Proc. Algorithms and Data Structures, 4th International Workshop. Proc. Algorithms and Data Structures, 4th International Workshop, Lect. Notes Comput. Sci., vol. 955 (1995), Springer), 122-134 · Zbl 1502.68303
[6] 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
[7] Chin, W.; Ntafos, S., Optimum watchman routes, (Proc. 2nd ACM Symposium on Computational Geometry (1986)), 24-33
[8] Chin, W.; Ntafos, S., Optimum watchman routes, Inf. Process. Lett., 28, 1, 39-44 (1988) · Zbl 0652.68042
[9] Chvátal, V., A combinatorial theorem in plane geometry, J. Comb. Theory, Ser. B, 18, 1, 39-41 (1997) · Zbl 0278.05028
[10] Dror, M.; Efrat, A.; Lubiw, A.; Mitchell, J. S.B., Touring a sequence of polygons, (Proc. 35th ACM Symposium on Theory of Computing (2003)), 473-482 · Zbl 1192.68354
[11] Dumitrescu, A.; Tóth, C. D., Watchman tours for polygons with holes, Comput. Geom. Theory Appl., 45, 7, 326-333 (2012) · Zbl 1239.65016
[12] Erickson, L. H.; LaValle, S. M., How many landmark colors are needed to avoid confusion in a polygon?, (Proc. IEEE International Conference on Robotics and Automation (2011)), 2302-2307
[13] Fakcharoenphol, J.; Rao, S.; Talwar, K., A tight bound on approximating arbitrary metrics by tree metrics, J. Comput. Syst. Sci., 69, 3, 485-497 (2004) · Zbl 1071.68082
[14] Garey, M. R.; Graham, R. L.; Johnson, D. S., Some NP-complete geometric problems, (Proc. 8th ACM Symposium on Theory of Computing (1976)), 10-22 · Zbl 0377.68036
[15] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. New York · Zbl 0411.68039
[16] Garg, N.; Konjevod, G.; Ravi, R., A polylogarithmic approximation algorithm for the group Steiner tree problem, J. Algorithms, 37, 1, 66-84 (2000) · Zbl 0962.68136
[17] Gewali, L. P.; Ntafos, S., Covering grids and orthogonal polygons with periscope guards, Comput. Geom. Theory Appl., 2, 6, 309-334 (1993) · Zbl 0774.68058
[18] Giyora, Y.; Kaplan, H., Optimal dynamic vertical ray shooting in rectilinear planar subdivisions, (Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (2007)), 19-28 · Zbl 1302.68288
[19] Hanan, M., On Steinerʼs problem with rectilinear distance, SIAM J. Appl. Math., 14, 255-265 (1966) · Zbl 0151.33205
[20] Henry-Labordere, A. L., The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem, RAIRO, B-2, 43-49 (1969) · Zbl 0187.14002
[21] Hershberger, J.; Suri, S., A pedestrian approach to ray shooting: Shoot a ray, take a walk, J. Algorithms, 18, 3, 403-431 (1995) · Zbl 0828.68121
[22] Hoffmann, F., Private communication, (The European Workshop on Computational Geometry (EuroCGʼ00). The European Workshop on Computational Geometry (EuroCGʼ00), Eilat, Israel (2000))
[23] Jonsson, H., The Traveling Salesman Problem for lines in the plane, Inf. Process. Lett., 82, 3, 137-142 (2002) · Zbl 1013.68265
[24] Kosowski, A.; Małafiejski, M.; Żyliński, P., Cooperative mobile guards in grids, Comput. Geom. Theory Appl., 37, 2, 59-71 (2007) · Zbl 1121.65021
[25] Mata, C. S.; Mitchell, J. S.B., Approximation algorithms for geometric tour and network design problems, (Proc. 11th ACM Symposium on Computational Geometry (1995)), 360-369
[26] Mitchell, J. S.B., Geometric shortest paths and network optimization, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier), 633-701 · Zbl 0941.68137
[27] Mitchell, J. S.B., Approximating watchman routes, (Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (2013)), 844-855 · Zbl 1422.68254
[28] Ntafos, S., On gallery watchmen in grids, Inf. Process. Lett., 23, 2, 99-102 (1986) · Zbl 0609.68048
[29] OʼRourke, J., Art Gallery Theorems and Algorithms (1987), Oxford University Press: Oxford University Press New York · Zbl 0653.52001
[30] Papadimitriou, C. H., Euclidean Travelling Salesman Problem is NP-complete, Theor. Comput. Sci., 4, 3, 237-244 (1977) · Zbl 0386.90057
[31] Reich, G.; Widmayer, P., Beyond Steinerʼs problem: a VLSI oriented generalization, (Proc. 15th International Workshop on Graph-Theoretic Concepts in Computer Science. Proc. 15th International Workshop on Graph-Theoretic Concepts in Computer Science, Lect. Notes Comput. Sci., vol. 411 (1990), Springer), 196-210 · Zbl 0768.68176
[32] Saksena, J. P., Mathematical model of scheduling clients through welfare agencies, CORS J., 8, 3, 185-200 (1970) · Zbl 0211.52002
[33] Shermer, T. C., Recent results in art galleries, Proc. IEEE, 80, 9, 1384-1399 (1992)
[34] Slavik, P., The errand scheduling problem (1997), University of Buffalo, CSE Technical Report 97-02
[35] Tan, X., Fast computation of shortest watchman routes in simple polygons, Inf. Process. Lett., 77, 1, 27-33 (2001) · Zbl 1003.68174
[36] Tan, X., A linear-time 2-approximation algorithm for the watchman route problem for simple polygons, Theor. Comput. Sci., 384, 1, 92-103 (2007) · Zbl 1124.68118
[37] Tan, X.; Hirata, T.; Inagaki, Y., Corrigendum to ‘An incremental algorithm for constructing shortest watchman routes’, Int. J. Comput. Geom. Appl., 9, 3, 319-323 (1999) · Zbl 0959.68129
[38] Tan, X.; Jiang, B., Minimization of the maximum distance between the two guards patrolling a polygonal region, (Proc. 6th International Frontiers of Algorithmics Workshop. Proc. 6th International Frontiers of Algorithmics Workshop, Lect. Notes Comput. Sci., vol. 7285 (2012), Springer), 47-57 · Zbl 1304.68187
[39] Tóth, C. D., Illumination in the presence of opaque line segments in the plane, Comput. Geom. Theory Appl., 21, 3, 193-204 (2002) · Zbl 0998.68194
[40] Tóth, C. D., Illuminating disjoint line segments in the plane, Discrete Comput. Geom., 30, 3, 489-505 (2003) · Zbl 1048.52013
[41] Urrutia, J., Art gallery and illumination problems, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier), 973-1027 · Zbl 0941.68138
[42] Xu, N., Complexity of minimum corridor guarding problems, Inf. Process. Lett., 112, 17-18, 691-696 (2012) · Zbl 1248.68225
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.