Voronoi Cell and Voronoi Diagram

Question

Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x and V(y) be the Voronoi cell of y. Prove or disprove that V(x) and V(y) share an edge in Vor(P ).

Here,as per my understanding, the shortest edge xy means that no other edge with one red endpoint and one blue endpoint is shorter. However, there may be edges with both red endpoints or both blue endpoints that are much shorter.

Answer 1

Let us assume that $P$ is in general position (no three points colinear, no four points cocircular) to make things easier.

As the Voronoi diagram is the dual of the Delaunay triangulation, this is the same as asking if the edge $xy$ is in the Delaunay triangulation of $P$.

You might know the following characterisation:

An edge $(a,b)$ is in the Delaunay triangulation of $P$ if and only if there is a disk whose boundary passes through $a$ et $b$ containing no other point of $P$ on its boundary or in its interior.

So let us take a look at the edge $(x,y)$ and let us draw the circle/disk whose diagonal is $(x,y)$.

Notice that if any point other than $x$ or $y$ is in the disk, then it is closer to both $x$ and $y$ then they are to each-other. Thus there is no such point in $P$, as it can't be red nor blue by definition of $(x,y)$. So this disk contains no other point of $P$, which means $(x,y)$ is an edge of the Delaunay triangulation, thus it is an edge of the Voronoi Diagram.

(There was no real need to make a detour through Delaunay triangulations as by duality the characterisation works just as well for Voronoi diagrams but I have always seen that characterisation stated in terms of Delaunay triangulations)