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

H. Edelsbrunner, A. Glazyrin, O. Musin, A. Nikitenko, Combinatorica 37 (2017) 887–910.


Journal Article | Published | English
Author
Department
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.
Publishing Year
Date Published
2017-10-01
Journal Title
Combinatorica
Acknowledgement
This research is partially supported by the Russian Government under the Mega Project 11.G34.31.0053, by the Toposys project FP7-ICT-318493-STREP, by ESF under the ACAT Research Network Programme, by RFBR grant 11-01-00735, and by NSF grants DMS-1101688, DMS-1400876.
Volume
37
Issue
5
Page
887 - 910
ISSN
IST-REx-ID

Cite this

Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. The Voronoi functional is maximized by the Delaunay triangulation in the plane. Combinatorica. 2017;37(5):887-910. doi:10.1007/s00493-016-3308-y
Edelsbrunner, H., Glazyrin, A., Musin, O., & Nikitenko, A. (2017). The Voronoi functional is maximized by the Delaunay triangulation in the plane. Combinatorica, 37(5), 887–910. https://doi.org/10.1007/s00493-016-3308-y
Edelsbrunner, Herbert, Alexey Glazyrin, Oleg Musin, and Anton Nikitenko. “The Voronoi Functional Is Maximized by the Delaunay Triangulation in the Plane.” Combinatorica 37, no. 5 (2017): 887–910. https://doi.org/10.1007/s00493-016-3308-y.
H. Edelsbrunner, A. Glazyrin, O. Musin, and A. Nikitenko, “The Voronoi functional is maximized by the Delaunay triangulation in the plane,” Combinatorica, vol. 37, no. 5, pp. 887–910, 2017.
Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. 2017. The Voronoi functional is maximized by the Delaunay triangulation in the plane. Combinatorica. 37(5), 887–910.
Edelsbrunner, Herbert, et al. “The Voronoi Functional Is Maximized by the Delaunay Triangulation in the Plane.” Combinatorica, vol. 37, no. 5, Springer, 2017, pp. 887–910, doi:10.1007/s00493-016-3308-y.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar