The following exercise has been handed out to students I supervise:
Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of points. The algorithm should run in time $o(n^2)$.
There is a (relatively) simple divide and conquer algorithm that solves the task in time $\Theta(n \log n)$.
Question 1: Is there an algorithm that solves the given problem exactly in worst-case time $\mathcal{o}(n \log n)$?
What made me suspect that this might be possible is a result I remember to have seen in some talk (reference appreciated). It stated something along the lines of that not more than a constant number $c \in \mathbb{N}$ of points can be arranged in the plane around some point $p$ inside a circle of radius $r \in \mathbb{R}$, with $r$ the minimal distance between any two of the involved points. I think $c=7$, the points forming a equilateral hexagon with $p$ in the center (in the extreme case).
In that case, the following algorithm should solve them problem in $n$ steps.
fun mindist [] | p::[] = INFINITY
| mindist p1::p1::[] = dist(P[0], P[1])
| mindist p::r = let m = mindist(r) in
min(m, nextNeighbour(p, r, m))
end
Note that this is (claimed to be) in linear time because only a constant number of points in r
can be no farer away than m
from p
(assuming above statement); only these points have to be investigated for finding a new minimum. There is a catch, of course; how do you implement nextNeighbour
(maybe with preprocessing in linear time)?
Question 2: Let a set of points $R$ and a point $p \notin R$. Let $m \in \mathbb{R}$ with
$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$
and
$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$.
Assume $R_{p,m}$ is finite. Is it possible to find $p' \in R_{p,m}$ with minimal distance from $p$ in (amortised) time $\mathcal{O}(1)$? (You may assume $R$ to be constructed by adding investigated points $p$ one by one.)