The Delaunay triangulation is the straight-line dual of the Voronoi diagram. This means you can use a Voronoi diagram to generate a Delaunay triangulation and you can use a Delaunay triangulation to generate a Voronoi diagram. The process of generating a Voronoi diagram from the Delaunay triangulation is called Naive Algorithm. [Ringler]
Red = Delaunay triangulation, Black = Voronoi diagram
Image Source: [Wikipedia]
When you read the topic post on Delaunay triangulation, you found that we circumscribe four co-circular points on the Delaunay triangulation. The edges that connect these circumscibed points have perpendicular bisectors. These perpendicular bisectors represent the edges of our Voronoi diagram! And, where they intersect is a site on the Voronoi diagram. [Mitchell]
Each edge of a triangle interior to the convex hull shares its edges with adjacent triangles. If a point within the convex hull were not contained by a triangle, then, projecting a line out from that point in any direction would cross an edge which was not shared with any other triangle. This is a contradiction, therefore all points within the hull are contained by exactly one triangle of the dual. [Fortune]
Image Source: [Wikipedia]
A more detailed proof of how Delaunay triangulation can be used to generate Voronoi diagrams here.
Resources
Fortune, Steven. “Voronoi Diagrams and Delaunay Triangulations.” Discrete and Computational Geometry, CRC Press, 2017, pp. 705 - 721. csun.edu, http://www.csun.edu/~ctoth/Handbook/chap27.pdf. Accessed 2020.
Mitchell, Joseph. “Voronoi and Delaunay Diagrams.” An Introduction to Computational Geometry, State University of New York, http://www.ams.sunysb.edu/~jsbm/courses/345/13/lecture-Voronoi.pdf. Accessed 2020.
Ringler, Todd. “Introduction to Voronoi Diagrams and Delaunay Triangulations.” Clasp Research, Los Almos National Laboratory, 2008, http://clasp-research.engin.umich.edu/groups/admg/ASP_Summer_Colloquium/25-Ringler-VoronoiDelaunay.pdf. Accessed 2020.
Wikipedia. “Delaunay Triangulation.” Wikipedia, Wikipedia, 2020, https://en.wikipedia.org/wiki/Delaunay_triangulation#Applications. Accessed 2020.
Comments