An optimal bound for conforming quality triangulations: (extended abstract)

ABSTRACT

This paper shows that for any plane geometric graph G with n vertices, there exists a triangulation T conforms to G , i.e. each edge of G is the union of some edges of T , where T has O(n2) vertices with angles of its triangles measuring no more than (11/15)&pgr;. Additionally, T can be computed in O(n2logn) time. The quadratic bound on the size of its vertex set is within a constant factor of worst case optimal.

REFERENCES

• BaAz76: I. Babu~ka and A. K. Aziz. On the angle condition in the finite element method. SIAM J. Numer. Anal. 13 (1976), 214-226.
• BaLi84: R. E. Barnhill and F. F. Little. Three and fourdimensional surfaces. Rocky Mountain J. Math. 14 (1984), 77-102.
• BDE92: Marshall Bern , David Dobkin , David Eppstein, Triangulating polygons without large angles, Proceedings of the eighth annual symposium on Computational geometry, p.222-231, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142722]
• BEG90: M. Bern, D. Eppstein and J. Gilbert. Provably good mesh generation. In "Proc. 31st Ann. IEEE Sympos. Found. Comput. Sci., 1990', 231-241. To appear in J. Comp. System Science.
• BeEp91: M. Bern and D. Eppstein. Polynomial-size nonobtuse triangulation of polygons. Intl. J. Comput. Geom. Appl. 2(3) (1992), 241-255.
• BeEp92: M. Bern and D. Eppstein. Mesh Generation and Optimal Triangulation. In Computing in Euclidean Geometry, D. Z. Du and F. K. Hwang, eds., World Scientific, Singapore, 1992, 23-90.
• BMR94: Marshall Bern , Scott Mitchell , Jim Ruppert, Linear-size nonobtuse triangulation of polygons, Proceedings of the tenth annual symposium on Computational geometry, p.221-230, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177974]
• Bois88: Jean-Daniel Boissonnat, Shape reconstruction from planar cross sections, Computer Vision, Graphics, and Image Processing, v.44 n.1, p.1-29, Oct. 1988 [doi>10.1016/S0734-189X(88)80028-8]
• Cave74: J. Cavendish. Automatic triangulation of arbitrary planar domains for the tinite element method. Intl. J. Numer. Methods Engrg. 8 (1974), 679-696.
• Dey91: Tamal Krishna Dey, Decompositions of polyhedra in three dimensions, Purdue University, West Lafayette, IN, 1992
• EdTa93: H. Edelsbrunner and T. S. Tan. An upper bound for conforming Delaunay triangulations. Discrete Comput. Geom. 10 (1993), 197-213.
• ETW92: Herbert Edelsbrunner , Tiow Seng Tan , Roman Waupotitsch, An O(n2logn) time algorithm for the minmax angle triangulation, SIAM Journal on Scientific and Statistical Computing, v.13 n.4, p.994-1008, July 1992 [doi>10.1137/0913058]
• Greg75: J.A. Gregory. Error bounds for linear interpolation on triangles. The Mathematics of Finite Element and Applications II, J. R. Whiteman, ed., Academic Press, NY, 1975, 163-170.
• Laws77: C. L. Lawson. Software for C1 surface interpolation. In Math. Software IiI, J. R. Rice, ed., Academic Press, 1977, 161-194.
• MeSo92: 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]
• Mitc93a: Scott Alan Mitchell, Mesh generation with provable quality bounds, Cornell University, Ithaca, NY, 1993
• Mitc93b: S. A. Mitchell. Refining a triangulation of a planar straight-line graph to eliminate large angles. In "Proc. 34th Ann. IEEE Sympos. Found. Comput. Sci., 1993', 583-591.
• Mitc94: S. A. Mitchell. Finding a covering triangulation whose maximum angle is provably small, in "Proc. 17th Ann. Computer Science Conference, ACSC-17, 1994".
• Rupp93: Jim Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.83-92, January 25-27, 1993, Austin, Texas, United States
• Tan93: Tiow-Seng Tan, Optimal two-dimensional triangulations, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• Tan94: T.S. Tan. An optimal bound for conforming quality triangulations. Techn. Rep., Dept. Inform. Sys. & Comput. Sci., National Univ. Singapore, Singapore, 1994.

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.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory