A Characterization of Link-2 LR-visibility Polygons with Applications - Discrete and Computational Geometry and Graphs - page 171

Finally, our result may also find applications in simplifying the existing solutions
of other visibility problems. For instance, an O ( n 4 ) time algorithm has been
proposed for searching a polygonal region with two 1-searchers [ 11 ]. The time
bound might further be improved to O ( n 3 )oreven O ( n 2 ), say, by characterizing
this search problem in terms of the non-redundant link-2 components. We are
working in this direction.
References
1. Bhattacharya, B.K., Ghosh, S.K.: Characterizing LR -visibility polygons and
related problems. Comput. Geom. Theory Appl. 18 , 19-36 (2001)
2. Chazelle, B., Guibas, L.: Visibility and intersection problem in plane geometry.
Discrete Comput. Geom. 4 , 551-581 (1989)
3. Das, G., Heffernan, P.J., Narasimhan, G.: LR-visibility in polygons. Comput.
Geom. Theory Appl. 7 (1), 37-57 (1997)
4. Ghosh, S.K.: Visibility Problems in the Plane. Cambridge University Press, Cam-
bridge (2007)
5. Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.: Linear time algo-
rithms for visibility and shortest path problems inside triangulated simple poly-
gons. Algorithmica 2 , 209-233 (1987)
6. Guibas, L.J., Hershberger, J.: Optimal shortest path queries in a simple polygon.
J. Comput. Syst. Sci. 39 , 126-152 (1989)
7. Hershberger, J.: A new data structure for shortest path queries in a simple polygon.
Inform. Process. Lett. 38 , 231-235 (1991)
8. Lee, J.H., Park, S.M., Chwa, K.Y.: Simple algorithms for searching a polygonal
region with flashlights. Inform. Process. Lett. 81 , 265-270 (2002)
9. Park, S.-M., Lee, J.-H., Chwa, K.-Y.: Visibility-based pursuit-evasion in a polyg-
onal region by a searcher. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.)
ICALP 2001. LNCS, vol. 2076, pp. 456-468. Springer, Heidelberg (2001)
10. O'Rourke, J.: Computational Geometry in C. Cambridge University Press, Cam-
bridge (1993)
11. Simov, B.H., Slutzki, G., LaValle, S.M.: Clearing a polygon with two 1-searchers.
Int. J. Comput. Geom. Appl. 19 , 59-92 (2009)
12. Suzuki, I., Yamashita, M.: Searching for mobile intruders in a polygonal region.
SIAM J. Comp. 21 (5), 863-888 (1992)
13. Tan, X.: A linear-time 2-approximation algorithm for the watchman route problem
for simple polygons. Theor. Compt. Sci. 384 (1), 92-103 (2007)
14. Tan, X., Jiang, B., Zhang, J.: Characterizing and recognizing LR -visibility poly-
gons. Discrete Appl. Math. 165 , 303-311 (2014)
15. 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)