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

DOI10.1007/S00493-016-3308-YzbMATH Open1399.52040arXiv1411.6337OpenAlexW1568423349MaRDI QIDQ722309FDOQ722309

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

Publication date: 23 July 2018

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (2)

• The farthest point Delaunay triangulation minimizes angles
• Title not available (Why is that?)

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)