2
$\begingroup$

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 |$?

1 Answers 1

3

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.

  • 0
    @fog: I assume by "denotes" you mean "implies".2012-07-01