# 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 < p < 1$). Is it known, for instance, whether this problem is $\Theta(n^2)$ for $0 < 1 < p$?

Edit: I will make the simplifying assumption that the balls' interiors do not intersect (though their boundaries may).

• If two balls have overlapping interiors, is their distance negative or zero? May 6, 2013 at 22:55
• One could argue that it should be negative, though if a ball's center is contained in another ball, this idea begins not to make sense. I will clarify that the balls are not overlapping except at boundary points. May 7, 2013 at 0:21
• The case of $p=2$ is easy because you can construct the resulting Voronoi diagram and scan the edges to find the closest pair. May 7, 2013 at 3:12
• @SureshVenkat: How do you take into account the radius of the balls in the Voronoi Diagram? May 7, 2013 at 6:23
• it's a generalized voronoi diagram that becomes the lower envelope of cones that are lowered below the plane depending on the ball radius May 7, 2013 at 6:27

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