1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Feb 25, 2022 at 9:45

1 Answer 1

1
$\begingroup$

No, since $pq$ may not be in the nearest neighbor graph.

p'(-3,1), p(-2,0), q(2,0), q'(3,1) made by https://www.overleaf.com/project/621a9034c0cff3abea32d201 and https://pixlr.com/e/#editor

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


Here is a useful property of Delaunay triangulation.

If a circle passing through two given points doesn't contain any other given points in its interior, the line segment between the two points is an edge of a Delaunay triangulation of the given points. If, furthermore, there is no given points on the boundary of the circle, that line segment is an edge of every Delaunay triangulation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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