Having the final Thiessen polygons, is it possible

Question

I'm trying to find a way to reverse the Voronoi algorithm.

Basically, having some connected shapes which mostly consist of triangles and squares, I'm trying to find the set of points which, by using the Voronoi algorithm would recreate the initial shapes.

Answer 1

Wouldn't finding the centroid of every triangle give you a point that is by definition, as far as possible from the other points.

Answer 2

Introduction. This problem has been solved in a paper by Biedl et al. in 2013 after a partial solution by Ash and Boker in 1985. In case your Voronoi nodes are all of odd degree then the algorithm by Ash and Bolker works for you.

First of all note that there might not be the point set but many point sets all having the same Voronoi diagram you ask for. For instance, consider this picture

taken from this website. The red point set and the blue point set give you the same black Voronoi diagram. (And, by the way, the straight skeletons of the red and blue polygon coincide with the Voronoi diagrams of the point sets as well.)

Overview of the algorithm. The rough idea is the following. Assume an oracle told you one candidate point in a Voronoi cell. Then you can mirror this point to neighboring Voronoi cells by the common edges between the neighboring cells, and keep on propagating.

But there could be troubles: The mirrored point may lie outside the neighboring cell. Also if you consider a Voronoi node and the incident cells then you can keep propagating the point around one cycle by the incident Voronoi edges, but you may not end up at the original point again.

So what the paper does is the following:

• It gives sufficient and necessary conditions for your input to form a Voronoi diagram.

• It tells you how to choose a valid starting point if such a point exists. Actually, it gives you set of all possible starting points.

The second part works roughly as follows: For each Voronoi cell one knows a "region" where the point has to lie by investigating the Voronoi nodes of the cell. Then take a spanning tree of the dual graph of the Voronoi diagram and choose an arbitrary root. For every cell you have a unique "mirroring path" to the "root cell". Apply the mirroring sequences of the regions mentioned above and intersect the mirror images.

The intersection is the set of all possible starting points. If it is empty then your input was not a Voronoi diagram.

Further simplification. In case your Voronoi nodes are of odd degree then the problem is much simpler. Consider Fig-4 in the paper by Biedl et al. to find out for each node the lines where the points must lie on. If a Voronoi cell has two nodes of odd degree then you can intersect these lines and get the single possible candidate point. You can do this for every Voronoi cell.