Find Shortest Pairwise Distance of Points in o(n log n)? 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&#39; \mid p&#39; \in R \wedge \mathrm{dist}(p, p&#39;) \leq m\}$.

Assume $R_{p,m}$ is finite. Is it possible to find $p&#39; \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.)
There is a randomized linear expected time algorithm by Rabin; see e.g. Rabin Flips a Coin on Lipton's blog.