# Delaunay to Voronoi ... and back?

Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points.

How about the other way around? Given a subdivision of (2D) space, how to determine unknown generators? Are there any common ways to do this?

Things I could think of were, assuming an underlying Delaunay triangulation, equal distances to Voronoi Vertices/"Delaunay Circumcenters", resulting in a system of quadratic equations.

Or searching for circles in the graph given by the Voronoi Vertices, and determining the center of the resulting polygons.

There is also a relationship to k-means clustering, as clusters defined by k-means, being the generators, yield a Voronoi Diagram in turn. This would leave me having to determine k and populate the regions with elements that are precisely not equidistant to two means.

I feel likely to be missing something very obvious and I would be happy for any direction in which to get started.

• Delaunay of $P$ is the dual graph of the Voronoi diagram of $P$. Since dual is symmetric, Voronoi of $P$ is the dual of Delaunay of $P$
– lox
Jul 9, 2019 at 15:55 