Abstract
We study a new class of visibility problems based on the notion of α-visibility. Given an angle α and a collection of line segments \(\ensuremath{{\cal S}}\) in the plane, a segment t is said to be α-visible from a point p, if there exists an empty triangle with one vertex at p and the side opposite to p on t such that the angle at p is α. In this model of visibility, we study the classical variants of point visibility, weak and complete segment visibility, and the construction of the visibility graph. We also investigate the natural query versions of these problems, when α is either fixed or specified at query time.
Research supported by NSERC, HPCVL and SUN Microsystems.
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
Aronov, B., Guibas, L., Teichmann, M., Zhang, L.: Visibility queries and maintenance in simple polygons. Discrete Comput. Geom. 27(4), 461–483 (2002)
Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1(1), 49–63 (1986)
Asano, T., Ghosh, S., Shermer, T.: Visibility in Plane in the Handbook in Computational Geometry. Elsevier Science (1999)
Bose, P., Lubiw, A., Munro, J.: Efficient visibility queries in simple polygons. In: Proc. 4th Canadian Conf. Comput. Geom., pp. 23–28 (1992)
Brunn, H.: Über Kerneigebiete. Math. Ann. 73, 436–440 (1913)
Chan, T.M.: Optimal partition trees. In: Proceedings of the 2010 Annual Symposium on Computational Geometry, SoCG 2010, pp. 1–10. ACM, N.Y. (2010)
ElGindy, H.A., Avis, D.: A linear algorithm for computing the visibility polygon from a point. J. Algorithms 2(2), 186–197 (1981)
Ghosh, S.: Visibility Algorithms in the Plane. Cambridge University Press (2007)
Ghosh, S., Mount, D.: An output-sensitive algorithm for computing visibility. SIAM J. Comput. 20, 888–910 (1991)
Gudmundsson, J., Morin, P.: Planar visibility: testing and counting. In: Proceedings of the 2010 Annual Symposium on Computational Geometry. ACM (2010)
Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2, 209–233 (1987)
Guibas, L., Motwani, R., Raghavan, P.: The robot localization problem. SIAM J. Comput. 26(4), 1120–1138 (1997)
Heffernan, P., Mitchell, J.: An optimal algorithm for computing visibility in the plane. SIAM J. Comput. 24(1), 184–201 (1995)
Keil, M., Mount, D., Wismath, S.: Visibility stabs and depth-first spiralling on line segments in output sensitive time. Int. J. Comput. Geometry Appl. 10(5), 535–552 (2000)
Lee, D.: Visibility of a simple polygon. Computer Vision, Graphics, and Image Processing 22(2), 207–221 (1983)
Matoušek, J.: Range searching with efficient hierarchical cuttings. Discrete & Computational Geometry 10, 157–182 (1993)
Melissaratos, E., Souvaine, D.: Shortest paths help solve geometric optimization problems in planar regions. SIAM Jl. Computing 21(4), 601–638 (1992)
Munro, J., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31, 762–776 (2002)
Nouri, M., Zarei, A., Ghodsi, M.: Weak Visibility of Two Objects in Planar Polygonal Scenes. In: Gervasi, O., Gavrilova, M.L. (eds.) ICCSA 2007, Part I. LNCS, vol. 4705, pp. 68–81. Springer, Heidelberg (2007)
Pocchiola, M., Vegter, G.: The visibility complex. Int. J. Comput. Geometry Appl. 6(3), 279–308 (1996)
Souvaine, D.: Computational geometry in a curved world (algorithm). PhD thesis. Princeton University, Princeton (1986), AAI8629439
Suri, S., O’Rourke, J.: Worst-case optimal algorithms for constructing visibility polygons with holes. In: Proceedings of the 1986 Annual Symposium on Computational Geometry, pp. 14–23 (1986)
Vegter, G.: The Visibility Diagram: A Data Structure for Visibility Problems and Motion Planning. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol. 447, pp. 97–110. Springer, Heidelberg (1990)
Zarei, A., Ghodsi, M.: Query point visibility computation in polygons with holes. Comput. Geom. Theory Appl. 39, 78–90 (2008)
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
Ghodsi, M., Maheshwari, A., Nouri, M., Sack, JR., Zarrabi-Zadeh, H. (2012). α-Visibility. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-31155-0_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31154-3
Online ISBN: 978-3-642-31155-0
eBook Packages: Computer ScienceComputer Science (R0)