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

  • 3
    $\begingroup$ If two balls have overlapping interiors, is their distance negative or zero? $\endgroup$
    – Jeffε
    May 6, 2013 at 22:55
  • $\begingroup$ 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. $\endgroup$ May 7, 2013 at 0:21
  • 1
    $\begingroup$ The case of $p=2$ is easy because you can construct the resulting Voronoi diagram and scan the edges to find the closest pair. $\endgroup$ May 7, 2013 at 3:12
  • $\begingroup$ @SureshVenkat: How do you take into account the radius of the balls in the Voronoi Diagram? $\endgroup$
    – J..y B..y
    May 7, 2013 at 6:23
  • 2
    $\begingroup$ it's a generalized voronoi diagram that becomes the lower envelope of cones that are lowered below the plane depending on the ball radius $\endgroup$ May 7, 2013 at 6:27

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.