The Voronoi functional is maximized by the Delaunay triangulation in the plane

DOI10.1007/S00493-016-3308-YMaRDI QIDQ722309zbMATH OpenOpenAlexFDO

Authors Herbert Edelsbrunner, Alexey Glazyrin, Oleg R. Musin, Anton V. Nikitenko

Publication date 23 July 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6337

zbMATH Keywords

optimalityDelaunay triangulationmaximumEuclidean planeVoronoi functional

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)

Abstract: We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.

Recommendations

• Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\)
• MAXIMIZING A VORONOI REGION: THE CONVEX CASE
• scientific article; zbMATH DE number 1979535
• On the optimality of functionals over triangulations of Delaunay sets
• scientific article; zbMATH DE number 2066953
• The farthest point Delaunay triangulation minimizes angles
• An optimal algorithm for realizing a Delaunay triangulation
• Combinatorial Geometry and Graph Theory
• Functionals on triangulations of Delaunay sets
• scientific article; zbMATH DE number 176773

Cites work

• A spectral characterization of the Delaunay triangulation
• Functionals on triangulations of Delaunay sets
• Geometry and topology for mesh generation
• Minimal roughness property of the Delaunay triangulation
• Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\)

Cited in

(2)

• The farthest point Delaunay triangulation minimizes angles
• scientific article; zbMATH DE number 1516568 (Why is no real title available?)

This page was built for publication: The Voronoi functional is maximized by the Delaunay triangulation in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722309)