A generalization of the geometric closest pair problem to balls In one version of the classical closest pair problem, one is given a set $S \subseteq \mathbb{R}^2$ and asked to find distinct $x, y \in S$ such that $\|x - y\|$ is minimized for some norm $\| \cdot \|$. This problem admits a well-known $O(n \log n)$ divide and conquer solution for $L^p$ spaces (Wikipedia).

Instead of a point set, I have instead a finite set of closed balls $S = \{B_{r_i} (\mathbf{x}_i) : \mathbf{x}_i \in \mathbb{R}^2\}$, and I would like to solve the associated distance problem. That is, for a given $p$, I want to find distinct $i$, $j$ such that the distance between $B_{r_i}(\mathbf{x}_i)$ and $B_{r_j}(\mathbf{x}_j)$ is minimal.

I have been unable to adapt the divide and conquer technique to this situation. Has any work been done on this problem? I care specifically about an asymptotically fast solution for the case $p = 1$, though I am also interested in the general solution (my examples and scribblings so far indicate that the case $1 \leq p \leq \infty$ may be easier than the case $0 &lt; p &lt; 1$). Is it known, for instance, whether this problem is $\Theta(n^2)$ for $0 &lt; 1 &lt; p$?

Edit: I will make the simplifying assumption that the balls' interiors do not intersect (though their boundaries may).
As Suresh says in his comment, you can extract the closest pair from the additively-weighted Voronoi diagram of the centers of the balls.  The closest pair of balls (in your case, diamonds) will have adjacent Voronoi regions.

The additively weighted Voronoi diagram of $n$ points in the plane can be constructed in $O(n\log n)$ time with high probability using a standard randomized incremental algorithm.  The same algorithms work, with only minor modifications, for diagrams in the Euclidean metric ($L_2$), the Manhattan metric ($L_1$), the supremum metric ($L_\infty$), or the $L_p$ metric for any other fixed $p\ge 1$.