Given a Voronoi diagram, find its sites

3
votes

We are given a Voronoi diagram in a form of DCEL (Doubly Connected Edge List), but without the actual sites for which the Voronoi diagram is built (just Voronoi vertexs, edges and faces).

The question is under what conditions can we (re)construct the set of points for which the given diagram was build and give the algorithm that does this.

What i know so far:

  • If we would figure out just one site, we could find all the others by drawing circles (we know that each Voronoi vertex is a center of an empty disc that has three sites on its circle)
  • I know how Fortunes (sweep) algorithm for constructing the Voronoi diagram works if we are given the sites

This problem is homework, so I am looking only for hints and tips to push me in the right direction.

2
computational-geometryvoronoi
It would seem that what you know is basically all you need: Since every voronoi vert is at a center of circle with 3+ sites, that means in order to maintain that vert, you can only scale that circle about it's center (no rotation,skew or translation). What happens if there is another neighboring circle that shares 2+ sites with the first circle, as you scale the first circle? Specifically, arc length between sites on the second circle will change? – Nicko Po
Without thinking further, i would guess, four non-collinear verts guarantees unique solution? – Nicko Po
@NickoPo Thank you for your anwser. Not sure I understand, but it seems to me you are decribing an algorithm to get the sites if one of the sites is given (also what is arch length between sites?). Maybe I was not really clear, but I already know how to find sites if one is given. The question is what if none of the sites are given. – rock90

2 Answers

0
votes

Found the solution for finding the first two sites. Not sure about correctnes but the idea seems sound. Getting the rest of the sites is as stated trivial.

http://tylerneylon.com/blog/2008/06/turning-convex-partition-into-voronoi.html

0
votes

I think you can solve the next linear program:

min 0

s.t. (ai*xj+bi*yj+c_i)/(a^2+b^2)=-(ai*xk+bi*yk+c_i)/(a^2+b^2), where ai*x+bi*y+c=0 is equation of line separating between cells j and k

Using some O(n log n) worst case or O(n) expected algorithm for 2D LP. And than if there is feasible solution these are sites (xi, yi) found by it, and if there is no - this was not Voronoi diagram