Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What can we say about two sets $A$ and $B$ if both of them have the same Voronoi diagram.

First, I thought if the Voronoi diagram are equal so the sets also should be equal, but by definition, Voronoi diagram is determined by distances to a specified family of objects (subsets) in the space, so do the same distances mean the same sets?

Is $A = B$?

Or $\left | A \right | = \left | B \right |$?

share|cite|improve this question
up vote 3 down vote accepted

It's easy to see that you can't say that A = B. Consider 2 points. The Voronoi diagram consists of a single line(the perpendicular bisector of the 2 points). There are infinite pairs of points having the same perpendicular bisector. If all the points are distinct, the sizes of the sets would be equal. Since, each region in the Voronoi diagram corresponds to exactly 1 point from the set, the sizes of the sets must be equal.

share|cite|improve this answer
thank you very much, I thought it would be much harder – fog Jun 20 '12 at 12:28
On the other hand, any Voronoi diagram with at least one vertex is generated by a unique set of sites. So if there is at least one Voronoi vertex, you really do have $A=B$. – JeffE Jun 25 '12 at 13:28
@JeffE, equality of Voronoi edges and Voronoi vertices denotes the equality of sets $A=B$ – fog Jul 1 '12 at 12:53
@fog: I assume by "denotes" you mean "implies". – JeffE Jul 1 '12 at 20:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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