\input TR10ReviewFormat.tex

\begfile{STEdge.tex of October 20, 1983 10:04 pm --- Stolfi}

% Not developed further --- result was already known!

\titlestuff{

\title{A Note on the Shortest Distance\cp
  Between Two Sets of Points}
\shorttitle{Shortest distance}
\author{Jorge Stolfi and Leo J. Guibas}
\institution{Stanford University and Xerox PARC}

\abstract{We show that for any two sets of points $S$ and $T$ on the plane, the shortest distance between a point in $S$ and a 
point and $T$ is realized by an edge of the Delaunay triangulation of $S\un T$. This gives $O(n\log n)$ algorithms for finding the 
closest $S$--$T$ pair, and for constructing the minimum Euclidean spanning tree of a given set of points.}

 }
 
% Reference macros

\def\Prim{Prim}
\def\Krus{Krus}
\def\Dijk{Dijk}
\def\GuiSto{GuiSto}
\def\Vor{Vor}

\section {1. The closest $S$--$T$ pair}

The {it Voronoi diagram} of a set $P$ of points in the plane is a well-known concept [\Vor?]. Its dual is the {\it Delaunay 
triangulation}, in which two points of $P$ are connected iff the corresponding regions of the Voronoi diagram share an edge. We 
recall the following property of Delaunay triangulations:

\theorem{1}{For any two points $p, q\in P$, the segment $pq$ is an edge of the Delaunay triangulation iff there is a circle that 
passes through $p$ and $q$, and contains no other point of $P$ (neither on its boundary nor in its interior).}

\mfig4cm
\proof{The segment $pq$ is an edge of the Delaunay triangulation iff there is some point $c$ of the plane that is on the boundary 
of exactly two regions of the Voronoi diagram, those corresponding to $p$ and $q$. But this is equivalent to saying that $p$ and 
$q$ are equidistant from $c$, and all other points of $P$ are further away from $c$ that those two; i.e., the circle with center 
$c$ and radius $cp$ passes through $p$ and $q$, and all other points of $P$ are outside it.}

For any two finite and nonempty sets $S$ and $T$ of points in the plane, the {\it distance}. between them is the minimum of 
$\dist(s, t)$ for $s\in S$ and $t\in T$. A {\it closest $S$--$T$ pair} is a pair $s$, $t$ that realizes this minimum distance. The 
following is a useful fact about such pairs:

\theorem{2}{Any closest $S$--$T$ pair is an edge of the Delaunay triangulation.}

\mfig4cm
\proof{Let $s\in S$ and $t\in T$ be a closest $S$--$T$ pair. By definition, the circle $C
s$ with center $s$ and radius $st$ must 
not contain any point of $T$; and, similarly, the circle $C
t$ with center $t$ and radius $ts$ contains no point of $S$. Therefore, 
the ``lune'' $C
t\inte C
s$ contains no pont of $S\un T$. We conclude that the circle $C
{st}$ with diameter $st$ passes through 
$s$ and $t$, and all other points of $S\un T$ are outside it, i.e. that $st$ is an edge of the Delaunay triangulation of $S\un T$.}
\endmfig

By using any of the asymptotically optimal algorithms in the literature [?, \GuiSto?], we can construct the Delaunay triangulation 
of $S\un T$ in $O(n\log n)$ time, where $n=\leftv S\rightv+\leftv T\rightv$. Since the Delaunay diagram has $O(n)$ edges, by a 
simply enumerating them we can find a closest $S$--$T$ pair (indeed, all of them) in $O(n\log n)$ total time.

\section {2. The minimum Euclidean spanning tree}

Given any graph whose vertices are points of the plane, we define the {\it length} of any of its edges as the Euclidean distance 
between its two endpoints. A {it minimal Euclidean spanning tree} (MEST) for a set $P$ of points of $n$ in the plane is defined as 
a tree having those points for vertices and whose total edge cost is minimum. Such a tree can be constructed by applying any 
general-purpose minimum spanning tree algorithm [\Prim? \Dijk? \Krus?] to the complete graph with vertex set $P$. However, since 
this graph has $O(n^2)$ edges, these algorithms would take at least $O(n^2)$.

A well-known property of minimum spanning trees in general is the following:

\lemma{3}{Let $e$ be any edge of a minimum spanning tree $\Tscr$ of a graph $\Gscr$, and $S$, $T$ be the vertex sets of the two 
components of $\Tscr-e$. Then, among all edges of $\Gscr$ connecting $S$ to $T$, $e$ has minimum cost.}

This property has an important consequence:

\theorem{4}{Any MEST for a point set $P$ is a spanning tree of the Delaunay triangulation of $P$.}
\proof{By lemma 3, every edge $e$ of a MEST for $P$ is a minimum-cost $S$--$T$ edge of the complete graph with vertices $P$ (that 
is to say, the endpoints of $e$ are a closest $S$--$T$ pair), for some partition $P=S\un T$. By theorem 2, all such edges are edges 
of the Delaunay triangulation of $P$, hence the result follows.}

Therefore, a MEST for a point set $P$ can be constructed in $O(n\log n)$ time, by first constructing the Delaunay triangulation of 
$P$ and then applying Prim's (Kruskal's?) algorithm to it.

\section {REFERENCES}

\par\vfill\eject\end