Abstract
LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take Θ(n 2) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai: Visibility of disjoint polygons.Algorithmica, Vol. 1, No. 1 (1986), pp. 49–63.
B. Baumgart: A polyhedral representation for computer vision.Proceedings of the AFIPS National Computer Conference, Anaheim, California, 1975, pp. 589–596.
B. Chazelle and L. Guibas: Visibility and intersection problems in plane geometry.Proceedings of the ACM Symposium on Computational Geometry, Baltimore, 1985, pp. 135–146.
B. Chazelle and J. Incerpi: Triangulation and shape complexity.ACM Transactions on Graphics, Vol. 3 (1984), pp. 135–152.
M. Garey, D. Johnson, F. Preparata, and R. Tarjan: Triangulating a simple polygon.Information Processing Letters, Vol. 7, No. 4 (1978), pp. 175–180.
S. K. Ghosh and D. M. Mount: An output sensitive algorithm for computing visibility graphs.Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, Los Angeles, 1987, pp. 11–19.
L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons.Algorithmica, Vol. 2, No. 2 (1987), pp. 209–233.
L. Guibas, E. McCreight, M. Plass, and J. Roberts: A new representation for linear lists.Proceedings of the Ninth ACM Symposium on Theory of Computing, Boulder, Colorado, 1977, pp. 49–60.
L. Guibas and J. Stolfi: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Transactions on Graphics, Vol. 4, No. 2 (1985), pp. 74–123.
S. Hertel and K. Mehlhorn: Fast triangulation of a simple polygon.Proceedings of the Conference on Foundations of Computing Theory, New York, 1983, pp. 207–218.
S. Huddleston and K. Mehlhorn: A new data structure for representing sorted lists.Acta Informatica, Vol. 17 (1982), pp. 157–184.
S. Suri: Private communication, 1986.
R. Tarjan and C. Van Wyk: AnO(n log logn)-time algorithm for triangulating a simple polygon.SIAM Journal on Computing, Vol. 17, No. 1 (1988), pp. 143–178.
E. Welzl: Constructing the visibility graph forn line segments inO(n 2) time.Information Processing Letters, Vol. 20 (1985), pp. 167–171.
Author information
Authors and Affiliations
Additional information
Communicated by Chee-Keng Yap.
This work was supported in part by a U.S. Army Research Office fellowship under agreement DAAG29-83-G-0020.
Rights and permissions
About this article
Cite this article
Hershberger, J. An optimal visibility graph algorithm for triangulated simple polygons. Algorithmica 4, 141–155 (1989). https://doi.org/10.1007/BF01553883
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01553883