Reverse-engineering Voronoi Diagrams

Shape and space, angle and circle properties, ...
Post Reply
User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Reverse-engineering Voronoi Diagrams

Post by elendiastarman » Fri Aug 14, 2009 5:34 am

Given a Voronoi diagram without any points marked, is there a simple and/or elegant way to reconstruct the set of points that were used to create it?

Also: Are there any two sets of points that will give the same Voronoi diagram?
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

rmillika
Posts: 39
Joined: Thu Apr 05, 2007 3:37 pm

Re: Reverse-engineering Voronoi Diagrams

Post by rmillika » Fri Aug 14, 2009 11:06 pm

1)For each region, bisect the sides. The bisectors will intersect in the point. This works if the diagram isn't too simple.
2)One example where you cannot reconstruct the points is n points equally spaced on a circle.
The diagram is n wedges that extend to infinity and you cannot determine the radius.
I believe it is true for n points on a circle even if they are not equally spaced.

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Reverse-engineering Voronoi Diagrams

Post by elendiastarman » Sat Aug 15, 2009 5:04 am

1) Too simple? How?
2) D'oh. Good example.
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Reverse-engineering Voronoi Diagrams

Post by daniel.is.fischer » Sat Aug 15, 2009 5:15 pm

Think a Voronoi diagram created by a two-point set or generally by points on a circle.
Or choose 0 < a, b < 1 and look at the Voronoi diagram created by the points having coordinates (2k [plusmn] a, 2m [plusmn] b) for integers k, m.
If the same diagram can be obtained by several sets, it is of course impossible to reverse-engineer.
If the cells are more complicated and irregular, you may be able to derive the points (I'm not sure how to interpret rmillika's algorithm, I think it's more complicated than stated).
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

User avatar
remy72
Posts: 296
Joined: Thu May 21, 2009 2:41 pm

Re: Reverse-engineering Voronoi Diagrams

Post by remy72 » Sat Aug 15, 2009 6:24 pm

you can use this method to compute one start point :
choose n>2 distinct adjacent cells : Ck is adjacent to Ck+1, and Cn is adjecent to C1
for a given point P1 in C1, we call Pk+1 the symmetric of Pk through the edge between Ck and Ck+1.
then you "just" have to solve the following equation: P1 is the symmetric of Pn through the edge between Cn and C1.

once you have the first start point, you can compute the start point in any adjacent cell via a simple axial symmetry, and iterate in order to visit all the cells.

rmillika
Posts: 39
Joined: Thu Apr 05, 2007 3:37 pm

Re: Reverse-engineering Voronoi Diagrams

Post by rmillika » Mon Aug 17, 2009 8:04 pm

daniel.is.fischer wrote: If the cells are more complicated and irregular, you may be able to derive the points (I'm not sure how to interpret rmillika's algorithm, I think it's more complicated than stated).
I don't think so for any of the bounded regions. Each bounded region is a convex polygon where each side is a portion of the bisector of the line segment between the source point inside the polygon and the source point in the neighboring polygon. So the bisector of each side must go through the source point within the polygon. If you construct two they will intersect at the source point within the region. This gets you all the source points within the bounded regions. If an unbounded region has any finite sides, the same argument applies to sides of finite length. If there are two of them you can find the source point. If there is only one, but you have the source point on the other side, you can reflect it in the side and find the source point. The only source points that you may not get are those in unbounded regions with no more than three sides which border on other unbounded regions.

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Reverse-engineering Voronoi Diagrams

Post by daniel.is.fischer » Tue Aug 18, 2009 2:34 pm

No. Consider the Voronoi diagram whose cells are the squares (a,b), (a+1,b), (a+1,b+1), (a,b+1); a, b &isin; Z. No unbounded regions.
You can generate that from (c+0.5,d+0.5); c, d &isin; Z or from (2c[plusmn]0.25, 2d[plusmn]0.25) (and many more).
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

rmillika
Posts: 39
Joined: Thu Apr 05, 2007 3:37 pm

Re: Reverse-engineering Voronoi Diagrams

Post by rmillika » Mon Aug 24, 2009 11:23 pm

A good example. You are right that things are more subtle than I thought.

Post Reply