Constrained Delaunay triangulations

ABSTRACT

Given a set of n vertices in the plane together with a set of noncrossing edges, the constrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimal &Ogr;(n log n) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (nonDelaunay) triangulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that should make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles in the plane and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.

REFERENCES

• CD85: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• Ch86: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• Ch87: L. P. Chew, Planar graphs and sparse w raphs for efficient motion planning in t e plane, manuscript.
• Fo86: S Fortune, A sweepline algorithm for Voronoi diagrams, Proceedings of the second annual symposium on Computational geometry, p.313-322, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10549]
• Ki79: D. G. Kirkoatrick, Efficient computation of continuous skeletons, Proceedings of the 20th Annual Svmoosium on the Foundations of -Computer Science, IEEE Computer Society (1979), 18-27.
• Le80: D. T. Lee, Proximity and reachibilit in the plane, Technical R- 31, Coordinated Science Report Laboratory, University of Illinois (1978).
• Ls80: D. T. Lee and 6. Schachter, Two algorithms for constructing Delaunay triangulations, International Journal of Computer and Information Sciences, 9:3 (1980) 219-242.
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Ya84: C. K. Yap,. An O(n lo 7 the Voronor diagram o n) algorithm for a set of sample curve segments, Technical Report, Courant Institute, New York University (Oct. 1984).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional 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

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Theory