A fast Las Vegas algorithm for triangulating a simple polygon

ABSTRACT

We present an algorithm that triangulates a simple polygon on n vertices in &Ogr;(n log* n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.

REFERENCES

• C87: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• C88: K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
• 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]
• ES: P. Erdos and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, New York, 1974.
• FM: A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
• GJPT: M. R. Garey, D. S. Johnson, F. P. Preparata and R. E. Tarjan, "Triangulating a simple polygon," Information Processing Letters, 7 (1978), 175-180.
• HW: D. Haussler and E. Welzl, "e-nets and simplex range queries," Discrete and Computational Geometry, 2 (1987), 127-151.
• HMRT: Kurt Hoffmann , Kurt Mehlhorn , Pierre Rosenstiehl , Robert E Tarjan, Sorting Jordan sequences in linear time using level-linked search trees, Information and Control, v.68 n.1-3, p.170-184, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80033-X]
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• R: M. M. Rao, Probability Theory with Applications, Academic Press, Orlando, Florida, 1984.
• TV: Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]

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:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  E. Data
  E.5 FILES
      Subjects: Sorting/searching

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

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

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Performance, Theory