# Prove an edge that minimizes the Euclidean distance crossing a cut is in the Delaunay triangulation

Let $$P$$ and $$Q$$ be two disjoint point sets in the plane. (Think of them as a red point set and a black point set.) Let $$p \in P$$ and $$q \in Q$$ be two points from these sets that minimize the Euclidean distance $$|pq|$$. Prove that $$pq$$ is an edge of $$\text{DT}(P\cup Q)$$.

I know this property of DT, the closest neighbor b to any point p is on an edge bp in the Delaunay triangulation since the nearest neighbor graph is a subgraph of the Delaunay triangulation.

Is this sufficient to prove the proposition above?

• Please don't delete your question after receiving an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful to others. Some may consider it impolite to delete your question after receiving an answer.
– D.W.
Commented Feb 25, 2022 at 9:45

No, since $$pq$$ may not be in the nearest neighbor graph.
For example, let $$P=\{(-3,1), (-2, -0)\}$$ and $$Q=\{(2,0), (3, 1)\}$$. Then $$p=(-2,0)$$ and $$q=(2,0)$$. However, the nearest neighbor graph, which consists of edge $$pp'$$ and edge $$qq'$$, does not contain edge $$pq$$.