Triangulating polygons without large angles

ABSTRACT

We show how to triangulate an n-vertex polygonal region—adding extra vertices as necessary—with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle is approximately as large as possible. Using O(n log n) triangles, we can also guarantee that the largest angle is no greater than 150°. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n1.85) triangles.

REFERENCES

• 1: I. Babu~ka and A. Aziz. On the angle condition in the finite element method, SIAM J. Numer. Anal. 13 (1976), 214-227.
• 2: Brenda S. Baker , Eric Grosse , Conor S. Rafferty, Nonobtuse triangulation of polygons, Discrete & Computational Geometry, v.3 n.2, p.147-168, Jan, 1988 [doi>10.1007/BF02187904]
• 3: R. Barnhill. Computer aided surface representation and design, Surfaces in CA GD, R. Barnhill and W. Boehm, eds., North-Holland, 1983, 1-24.
• 4: Marshall W. Bern , Herbert Edelsbrunner , David Eppstein , Sandra L. Mitchell , Tio Seng Tan, Edge Insertion for Optional Triangulations, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.46-60, April 06-10, 1992
• 5: Marshall Bern , David Eppstein, Polynomial-size nonobtuse triangulation of polygons, Proceedings of the seventh annual symposium on Computational geometry, p.342-350, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109686]
• 6: M. Bern and D. Eppstein. Mesh generation and optimal triangulation, to appear in Computing in Euclidean Geometry, D.-Z. Du and F.K. }{'Iwang, eds., World Scientific, 1992.
• 7: M. Bern, D. Eppstein, and J.R. Gilbert. Provably good mesh generation, 31st IEEE Foundations of Computer Science, 1990, 231-241.
• 8: Herbert Edelsbrunner , Tiow Seng Tan, An upper bound for conforming Delaunay triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.53-62, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142690]
• 9: Herbert Edelsbrunner , Tiow Seng Tan , Roman Waupotitsch, An O(n2log n) time algorithm for the MinMax angle triangulation, Proceedings of the sixth annual symposium on Computational geometry, p.44-52, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98535]
• 10: David Eppstein, Approximating the minimum weight triangulation, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.48-57, September 1992, Orlando, Florida, United States
• 11: C. M. Gold , T. D. Charters , J. Ramsden, Automated contour mapping using triangular element data structures and an interpolant over each irregular triangular domain, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.170-175, July 20-22, 1977, San Jose, California
• 12: J. Gregory. Error bounds for linear interpolation on triangles, The Mathematics o.f Finite Elements and Application H, J. R. Whiteman, ed., Academic Press, 1975, 163-170.
• 13: Elefterios A. Melissaratos , Diane L. Souvaine, Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes, Proceedings of the eighth annual symposium on Computational geometry, p.202-211, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142719]
• 14: Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
• 15: S. Salzberg, A. Delcher, D. Heath, and S. Kasif. Learning with a helpful teacher. 12th int. Joint Conf. Artificial Intelligence, 1991.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Verification