New methods for computing visibility graphs

ABSTRACT

Let S be a set of n non-intersecting line segments in the plane. The visibility graph GS of S is the graph that has the endpoints of the segments in S as nodes and in which two nodes are adjacent whenever they can “see” each other (i.e., the open line segment joining them is disjoint from all segments or is contained in a segment). Two new methods are presented to construct GS. Both methods are very simple to implement. The first method is based on a new solution to the following problem: given a set of points, for each point sort the other points around it by angle. It runs in time &Ogr;(n2). The second method uses the fact that visibility graphs often are sparse and runs in time &Ogr;(m log n) where m is the number of edges in GS. Both methods use only Ogr;(n) storage.

REFERENCES

• 1: 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]
• 2: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 3: Ghosh, S.K. and D.M. Mount, An output sensitive algorithm for computing visibility graphs, Proc. 28lh Syrup. on Foundations of Computer Science, Los Angeles, 1987, 11-19.
• 4: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 5: J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size, Proceedings of the third annual symposium on Computational geometry, p.11-20, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41960]
• 6: Der-Tsai Lee, Proximity and reachability in the plane., 1978
• 7: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 8: Overmars, M.H. and E. Welzl, Construction of sparse visibility graphs, Techn. Rep. RUU-CS- 87-9, Dept. of Computer Science, University of Utrecht, 1987.
• 9: Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]
• 10: Welzl, E~, Constructing the visibility graph for n line segments in O(n2) time, Inform. Proc./;el. 20 (1985), 107-171.

INDEX TERMS

Primary 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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Experimentation, Performance, Theory