2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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$ $\endgroup$
    – lox
    Jul 9, 2019 at 15:55

1 Answer 1

Reset to default
2
$\begingroup$

Unfortunately, you cannot generally reconstruct the generators from Voronoi polygons. Look at the four simple examples below: all have the same two Voronoi cells but different placement of the generators.

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to the site! $\endgroup$
    – Caleb Stanford
    Apr 17, 2020 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.