Abstract
Determining whether two segments s and t in a planar polygonal scene weakly see each other is a classical problem in computational geometry. In this problem we seek for a segment connecting two points of s and t without intersecting edges of the scene. In planar polygonal scenes, this problem is 3sum-hard and its time complexity is Ω(n 2) where n is the complexity of the scene. This problem can be defined in the same manner when s and t are any kind of objects in the plane. In this paper we consider this problem when s and t can be points, segments or convex polygons. We preprocess the scene so that for any given pair of query objects we can solve the problem efficiently. In our presented method, we preprocess the scene in O(n 2 + ε) time to build data structures of O(n 2) total size by which the queries can be answered in O(n 1 + ε) time. Our method is based on the extended visibility graph [1] and a range searching data structure presented by Chazelle et al. [2].
This work was partially supported by IPM school of computer science (contract: CS1385-2-01).
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
Suri, S., O’Rourke, J.: Worst-case optimal algorithms for constructing visibility polygons with holes. In: Symposium on Computational Geometry, pp. 14–23 (1986)
Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica 8(5&6), 407–429 (1992)
Gajentaan, A., Overmars, M.H.: On a class of o(n2) problems in computational geometry. Comput. Geom. 5, 165–185 (1995)
Wismath, S.K.: Computing the full visibility graph of a set of line segments. Inf. Process. Lett. 42(5), 257–261 (1992)
Welzl, E.: Constructing the visibility graph for n-line segments in o(n) time. Inf. Process. Lett. 20(4), 167–171 (1985)
Asano, T., Asano, T., Guibas, L.J., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1(1), 49–63 (1986)
Ghosh, S.K., Mount, D.M.: An output sensitive algorithm for computing visibility graphs. In: FOCS, pp. 11–19. IEEE Computer Society Press, Los Alamitos (1987)
Overmars, M.H., Welzl, E.: New methods for computing visibility graphs. In: Symposium on Computational Geometry, pp. 164–171 (1988)
Keil, M., Mount, D.M., Wismath, S.K.: Visibility stabs and depth-first spiralling on line segments in output sensitive time. Int. J. Comp. Geom. Appl. 10(5), 535–552 (2000)
Lee, D., Preparata, F.: Location of a point in a planar subdivision and its applications. SIAM Journal of Computing 6(3), 594–606 (1977)
Chazelle, B., Guibas, L.J.: Visibility and intersection problems in plane geometry. Discrete & Computational Geometry 4, 551–581 (1989)
Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L.J., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12(1), 54–68 (1994)
Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: Shoot a ray, take a walk. J. Algorithms 18(3), 403–431 (1995)
Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry, AMS Press, Providence, RI (1998)
Cheng, S.W., Janardan, R.: Space-efficient ray-shooting and intersection searching: algorithms, dynamization, and applications. In: SODA ’91. Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pp. 7–16. ACM Press, New York (1991)
Welzl, E.: Partition trees for triangle counting and other range searching problems. In: Symposium on Computational Geometry, pp. 23–33 (1988)
Matousek, J., Welzl, E.: Good splitters for counting points in triangles. J. Algorithms 13(2), 307–319 (1992)
Dobkin, D.P., Edelsbrunner, H.: Space searching for intersecting objects. J. Algorithms 8(3), 348–361 (1987)
Matousek, J.: Efficient partition trees. Disc. & Comp. Geom. 8, 315–334 (1992)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nouri, M., Zarei, A., Ghodsi, M. (2007). Weak Visibility of Two Objects in Planar Polygonal Scenes. In: Gervasi, O., Gavrilova, M.L. (eds) Computational Science and Its Applications – ICCSA 2007. ICCSA 2007. Lecture Notes in Computer Science, vol 4705. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74472-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-74472-6_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74468-9
Online ISBN: 978-3-540-74472-6
eBook Packages: Computer ScienceComputer Science (R0)