Abstract
The two-guard problem asks whether two guards can walk to detect an unpredictable, moving target in a polygonal region P, no matter how fast the target moves, and if so, construct a walk schedule of the guards. For safety, two guards are required to always be mutually visible, and thus, they move on the polygon boundary. Specially, a straight walk requires both guards to monotonically move on the boundary of P from beginning to end, one clockwise and the other counterclockwise.
The objective of this paper is to find an optimum straight walk such that the maximum distance between the two guards is minimized. We present an O(n 2 logn) time algorithm for optimizing this metric, where n is the number of vertices of the polygon P. Our result is obtained by investigating a number of new properties of the min-max walks and converting the problem of finding an optimum walk in the min-max metric into that of finding a shortest path between two nodes in a graph. This answers an open question posed by Icking and Klein.
Work by Tan was partially supported by Grant-in-Aid (23500024) for Scientific Research from Japan Society for the Promotion of Science, and work by Jiang was partially supported by National Natural Science Foundation of China under grant 61173034.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alt, H., Godau, M.: Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. & Appl. 5, 75–91 (1995)
Bespamyatnikn, B.: An optimal morphing between polylines. Int. J. Comput. Geom. & Appl. 12, 217–228 (2002)
Bhattacharya, B.K., Mukhopadhyay, A., Narasimhan, G.: Optimal Algorithms for Two-Guard Walkability of Simple Polygons. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 438–449. Springer, Heidelberg (2001)
Chazelle, B., Guibas, L.: Visibility and intersection problem in plane geometry. Discrete Comput. Geom. 4, 551–581 (1989)
Cook, A.F., Wenk, C.: Geodesic Fréchet distance inside a simple polygon. ACM Trans. Algo. 7(1) (2010)
Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introdution to algorithms, 2nd edn. The MIT Press (2001)
Efrat, A., Guibas, L.J., Har-Peled, S., Lin, D.C., Mitchell, J.S.B., Murali, T.M.: Sweeping simple polygons with a chain of guards. In: Proc., ACM-SIAM Sympos. Discrete Algorithms, pp. 927–936 (2000)
Ghosh, S.K.: Visibility algorithms in the plane. Cambridge University Press (2007)
Guibas, L.J., Latombe, J.C., Lavalle, S.M., Lin, D., Motwani, R.: Visibility-based pursuit-evasion in a polygonal environment. IJCGA 9, 471–493 (1999)
Heffernan, P.J.: An optimal algorithm for the two-guard problem. Int. J. Comput. Geom. & Appl. 6, 15–44 (1996)
Icking, C., Klein, R.: The two guards problem. Int. J. Comput. Geom. & Appl. 2, 257–285 (1992)
LaValle, S.M., Simov, B., Slutzki, G.: An algorithm for searching a polygonal region with a flashlight. Int. J. Comput. Geom. & Appl. 12, 87–113 (2002)
Lee, J.H., Park, S.M., Chwa, K.Y.: Searching a polygonal room with one door by a 1-searcher. Int. J. Comput. Geom. & Appl. 10, 201–220 (2000)
Suzuki, I., Yamashita, M.: Searching for mobile intruders in a polygonal region. SIAM J. Comp. 21, 863–888 (1992)
Tan, X.: A unified and efficient solution to the room search problem. Comput. Geom. Theory Appl. 40(1), 45–60 (2008)
Tan, X.: An efficient algorithm for the three-guard problem. Discrete Appl. Math. 158, 3312–3324 (2008)
Tan, X.: Sweeping simple polygons with the minimum number of chain guards. Inform. Process. Lett. 102, 66–71 (2007)
Tan, X.: The Two-Guard Problem Revisited and Its Generalization. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 847–858. Springer, Heidelberg (2004)
Tan, X., Jiang, B.: Optimum Sweeps of Simple Polygons with Two Guards. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol. 6213, pp. 304–315. Springer, Heidelberg (2010)
Tseng, L.H., Heffernan, P.J., Lee, D.T.: Two-guard walkability of simple polygons. Int. J. Comput. Geom. & Appl. 8(1), 85–116 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tan, X., Jiang, B. (2012). Minimization of the Maximum Distance between the Two Guards Patrolling a Polygonal Region. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds) Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol 7285. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29700-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-29700-7_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29699-4
Online ISBN: 978-3-642-29700-7
eBook Packages: Computer ScienceComputer Science (R0)