Finding the visibility graph of a simple polygon in time proportional to its size

ABSTRACT

Let P be a given simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in &Ogr;(m + n log log n) time, where m is the number of edges in the visibility graph. Because m can be as small as &Ogr;(n), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take &THgr;(n2) time.

REFERENCES

• AAGHI: Takao Asano , Tetsuo Asano , Leonidas Guibas , John Hershberger , Hiaroshi Imai, Visibility of disjoint polygons, Algorithmica, v.1 n.1, p.49-63, Jan. 1986 [doi>10.1007/BF01840436]
• B: B. Baumgart: UA polyhedral representation for computer vision." Proceedings of the AFIPS National Computer Conference, 1975, pp. 58Q- 596.
• CG: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• CI: B. Chazelle , J. Incerpi, Triangulation and shape-complexity, ACM Transactions on Graphics (TOG), v.3 n.2, p.135-152, April 1984 [doi>10.1145/357337.357340]
• GJPT: M. Garey, D. Johnson, F. Preparata, R. Tarjan: "Triangulating a simple polygon." Information Processing Letters, Vol. 7, No. 4 (1978)) pp. 175-180.
• GHLST: L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
• GMPR: Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803395]
• GS: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• HeM: Stefan Hertel , Kurt Mehlhorn, Fast Triangulation of Simple Polygons, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.207-218, August 21-27, 1983
• HuM: S. Huddleston and K. Mehlhorn: "A new data structure for representing sorted lists." Acta Informatica, Vol. 17 (1982), pp. 157-184.
• S: S. Suri: Private communication, 1986.
• TV: R. Tarjan and C. Van Wyk: "An O(n log log n)- time algorithm for triangulating simple polygons." Manuscript, July 1986.
• W: E. Welzl: 'Constructing the visibility graph for n line segments in O(ra2) time." Information Processing Letters, Vol. 20 (1985), pp. 167-171.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory