4
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ If two balls have overlapping interiors, is their distance negative or zero? $\endgroup$ – Jeffε May 6 '13 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$ – Eric Tressler May 7 '13 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$ – Suresh Venkat May 7 '13 at 3:12
  • $\begingroup$ @SureshVenkat: How do you take into account the radius of the balls in the Voronoi Diagram? $\endgroup$ – Jeremy May 7 '13 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$ – Suresh Venkat May 7 '13 at 6:27
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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