Abstract
In this paper we present new optimality results for the Delaunay triangulation of a set of points in ℝd. These new results are true in all dimensionsd. In particular, we define a power function for a triangulation and show that the Delaunay triangulation minimizes the power function over all triangulations of a point set. We use this result to show that (a) the maximum min-containment radius (the radius of the smallest sphere containing the simplex) of the Delaunay triangulation of a point set in ℝd is less than or equal to the maximum min-containment radius of any other triangulation of the point set, (b) the union of circumballs of triangles incident on an interior point in the Delaunay triangulation of a point set lies inside the union of the circumballs of triangles incident on the same point in any other triangulation of the point set, and (c) the weighted sum of squares of the edge lengths is the smallest for Delaunay triangulation, where the weight is the sum of volumes of the triangles incident on the edge. In addition we show that if a triangulation consists of only self-centered triangles (a simplex whose circumcenter falls inside the simplex), then it is the Delaunay triangulation.
Article PDF
Similar content being viewed by others
References
F. Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure,ACM Comput. Surveys 23 (1991), 345–405.
M. Bern and D. Eppstein, Mesh generation and optimal triangulation, inComputing in Euclidean Geometry (F. K. Hwang and D. Z. Du, eds.), World Scientific, Singapore, 1992, pp. 23–90.
K. Q. Brown, Voronoi diagrams from convex hulls,Inform. Process. Lett. 9 (1970), 223–228.
R. W. Cottle, Symmetric dual quadratic programs,Quart. Appl. Math. 21 (1963), 237–243.
E. F. D’Azevedo and R. B. Simpson, On optimal interpolation triangle incidences,SIAM J. Sci. Statist. Comput. 10 (1989), 1063–1075.
W. S. Dorn, Duality in quadratic programming,Quart. Appl. Math. 18 (1960), 155–162.
H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements,Discrete Comput. Geom. 1 (1986), 25–44.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987.
H. Edelsbrunner and E. P. Mucke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms,ACM Trans. Graphics 9 (1990), 66–104.
S. Fortune, A sweepline algorithm for Voronoi diagrams,Algorithmica 2(2) (1987), 153–174.
L. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Trans. Graphics 4 (1985), 74–123.
M. S. Karasick, D. Lieber, L. R. Nackman, and V. T. Rajan, Fast Visualization of Three-Dimensional Delaunay Meshes, RC 18347, IBM T. J. Watson Research Center, Yorktown Heights, NY, 1992.
C. L. Lawson, Generation of a Triangular Grid with Applications to Contour Plotting, Internal Technical Memorandum No. 299, Jet Propulsion Laboratory, Pasadena, CA, 1972.
S. Meshkat, J. Ruppert, and H. Li, Three-Dimensional automatic unstructured grid generation based on Delaunay tetrahedralization,Proc. Internat. Conf. on Numerical grid Generation, 1991, pp. 841–851.
F. P. Preparata, and M. I. Shamos,Computational Geometry—An Introduction, Springer-Verlag, New York, 1985.
V. T. Rajan. Optimality of the Delaunay triangulation in ℝd,Proc. 7th Ann. Symp. on Computational Geometry, 1991, pp. 357–363.
M. I. Shamos and D. Hoey, Closest-point problems,Proc. 16th Ann. IEEE Symp. on Foundations of Computer Science, 1975, pp. 151–162.
V. Srinivasan, L. R. Nackman, J. Tang, and S. N. Meshkat, Automatic mesh generation using the symmetric axis transformation of polygonal domains,Proc. IEEE,80(9) (1992), 1485–1501.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rajan, V.T. Optimality of the Delaunay triangulation in ℝd. Discrete Comput Geom 12, 189–202 (1994). https://doi.org/10.1007/BF02574375
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02574375