## Reverse-engineering Voronoi Diagrams

- elendiastarman
**Posts:**410**Joined:**Sat Dec 22, 2007 8:15 pm

### Reverse-engineering Voronoi Diagrams

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?

Also: Are there any two sets of points that will give the same Voronoi diagram?

Want some

3.14159265358979323846264338327950288419716939937510

58209749445923078164062862089986280348253421170679...?

3.14159265358979323846264338327950288419716939937510

58209749445923078164062862089986280348253421170679...?

### Re: Reverse-engineering Voronoi Diagrams

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.

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.

- elendiastarman
**Posts:**410**Joined:**Sat Dec 22, 2007 8:15 pm

### Re: Reverse-engineering Voronoi Diagrams

1) Too simple? How?

2) D'oh. Good example.

2) D'oh. Good example.

Want some

3.14159265358979323846264338327950288419716939937510

58209749445923078164062862089986280348253421170679...?

3.14159265358979323846264338327950288419716939937510

58209749445923078164062862089986280348253421170679...?

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

### Re: Reverse-engineering Voronoi Diagrams

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

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ètes sont là.

### Re: Reverse-engineering Voronoi Diagrams

you can use this method to compute one start point :

choose n>2 distinct adjacent cells : C

for a given point P

then you "just" have to solve the following equation: P

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.

choose n>2 distinct adjacent cells : C

_{k}is adjacent to C_{k+1}, and C_{n}is adjecent to C_{1}for a given point P

_{1}in C_{1}, we call P_{k+1}the symmetric of P_{k}through the edge between C_{k}and C_{k+1}.then you "just" have to solve the following equation: P

_{1}is the symmetric of P_{n}through the edge between C_{n}and C_{1}.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.

### Re: Reverse-engineering Voronoi Diagrams

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.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 interpretrmillika's algorithm, I think it's more complicated than stated).

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

### Re: Reverse-engineering Voronoi Diagrams

No. Consider the Voronoi diagram whose cells are the squares (a,b), (a+1,b), (a+1,b+1), (a,b+1); a, b ∈ Z. No unbounded regions.

You can generate that from (c+0.5,d+0.5); c, d ∈ Z or from (2c[plusmn]0.25, 2d[plusmn]0.25) (and many more).

You can generate that from (c+0.5,d+0.5); c, d ∈ Z or from (2c[plusmn]0.25, 2d[plusmn]0.25) (and many more).

Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

### Re: Reverse-engineering Voronoi Diagrams

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