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.

$\endgroup$
  • $\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 '19 at 15:55
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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to the site! $\endgroup$ – 6005 Apr 17 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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