Construction of the Voronoi Diagram and Secondary Polytope

2003/12/02 by Oleg R. Musin
Mathematics · #math.MG

paper · pdf

published as Voronoi Impact on Modern Science. Book 2. Kiev, Institute of Math., 1998, 105-114

arxiv created 2003/12/02 · arxiv updated 2009/12/01

Abstract

A set S of n points in general position in R^d defines the unique Voronoi diagram of S. Its dual tessellation is the Delaunay triangulation (DT) of S. In this paper we consider the parabolic functional on the set of triangulations of S and prove that it attains its minimum at DT in all dimensions. The Delaunay triangulation of S is corresponding to a vertex of the secondary polytope of S. We proposed an algorithm for DT's construction, where the parabolic functional and the secondary polytope are used. Finally, we considered a discrete analog of the Dirichlet functional. DT is optimal for this functional only in two dimensions.

Related

• Properties of the Delaunay Triangulation
• Anisotropic triangulations via discrete Riemannian Voronoi diagrams
• A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations
• Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions
• An obstruction to Delaunay triangulations in Riemannian manifolds