Linear-size nonobtuse triangulation of polygons

ABSTRACT

We give an algorithm for triangulating n-vertex polygonal regions (with holes) so that no angle in the final triangulation measures more than &pgr;/2. The number of triangles in the triangulation is only O(n), improving a previous bound of O(n2), and the worst-case running time is O(nlog2n). The basic technique used in the algorithm, recursive subdivision by disks, is new and may have wider application in mesh generation. We also report on an implementation of our algorithm.

REFERENCES

• 1: A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
• 2: I. Babu~ka and A. Aziz. On the angle condition in the finite element method. SIAM J. Numer. Analysis 13 (1976), 214-227.
• 3: 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]
• 4: R.E. Bank. PLTMG User's Guide. SIAM, 1990.
• 5: J.L. Bentley and J.B. Saxe. Decomposable searching problems: 1. Static-to-dynamic transformation. J. Algorithms i (1980), 30t{-358.
• 6: M. Bern, L.P. Chew, D. Eppstein, and J. Ruppert. Dihedral Bounds for Mesh Generation in High Dimensions. Manuscript, 1993.
• 7: 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]
• 8: M. Bern and D. Eppstein. Polynomial-size nonobtuse triangulation of polygons. Int. J. Comp. Geometry and Applications 2 (1992), 24!{-255.
• 9: M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Xerox PARC Tech. Report CSL-92-1. Also in Computing in Euchdean Geometry, World Scientific, Singapore, 1992.
• 10: M. Bern, D. Eppstein, and J.R. Gilbert. Provably good mesh generation. Proc. 31st IEEE $ymp. on Foundations of Computer Science, 1990, 231- 241. To appear in J. Comp. System Science.
• 11: H.S.M. Coxeter. Introduction to Geometry. John Wiley & Sons, 1961.
• 12: H. Edelsbrunner and T.S. Tan. An upper bound for conforming Delaunay triangulations. Discrete and Comp. Geom. 10 (1993), 197-213.
• 13: S. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica 2 (1987), 153-174.
• 14: M.T. Goodrich, C. ODfinlaing, and C.~ Yap. Computing the Voronoi diagram of a set of line segments in parallel. Algorithmica 9 (1993), 128-141.
• 15: MATLAB Reference Guide, The MathWorks, Inc., Natick, Massachusetts, 1992.
• 16: 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]
• 17: S.A. Mitchell. Refining a triangulation of a planar straight-line graph to eliminate large angles. Proc. 3~th Syrup. on Foundations of Computer Science, 1993, 583-591.
• 18: S.A. Mitchell. Finding a covering triangulation whose maximum angle is provably small. Proc. 17th Annual Computer Science Conference, Australian Comp. Science Comm. 16 (1994), 55-64.
• 19: J.-D. Mfiller. Proven angular bounds and stretched triangulations with the frontal Delaunay method. Proc. 11th AIAA Comp. Fluid Dynamics, Orlando, 1993.
• 20: S. Miiller, K. Kells, and W. Fichtner. Automatic rectangle-based adaptive mesh generation without obtuse angles. IEEE Trans. Computer-Aided Design 10 (1992), 855-863.
• 21: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 22: J.F. Randolph. Calculus and Analytic Geometry. Wadsworth, 1961, 373-374.
• 23: 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
• 24: Kenji Shimada , David C. Gossard, Computational Methods for Physically-based FE Mesh Generation, Proceedings of the IFIP TC5 / WG5.3 Eight International PROLAMAT Conference on Human Aspects in Computer Integrated Manufacturing, p.411-420, June 24-26, 1992
• 25: G. Strang and G.J. Fix. An Analysis of the Finite Element Method. Prentice Hall, 1973.
• 26: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 27: Stephen A. Vavasis, Stable Finite Elements for Problems with Wild Coefficients, Cornell University, Ithaca, NY, 1993

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.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory, Verification