<p>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.</p>

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

CC BY-SA 3.0
2013-05-07T14:29:31.540Z
2013-05-07T14:29:31.540Z
Jeffε
<p>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 (<a href="http://en.wikipedia.org/wiki/Closest_pair_of_points_problem" rel="nofollow">Wikipedia</a>).</p>

<p>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.</p>

<p>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$?</p>

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

CC BY-SA 3.0
2013-05-06T22:55:36.083Z
If two balls have overlapping interiors, is their distance negative or zero?
Jeffε
CC BY-SA 3.0
2013-05-07T00:21:27.037Z
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.
Eric Tressler
CC BY-SA 3.0
2013-05-07T03:12:53.187Z
The case of $p=2$ is easy because you can construct the resulting Voronoi diagram and scan the edges to find the closest pair.
Suresh Venkat
CC BY-SA 3.0
2013-05-07T06:23:01.083Z
@SureshVenkat: How do you take into account the radius of the balls in the Voronoi Diagram?
J.y B.y
CC BY-SA 3.0
2013-05-07T06:27:24.137Z
it's a generalized voronoi diagram that becomes the lower envelope of cones that are lowered below the plane depending on the ball radius
Suresh Venkat
CC BY-SA 3.0
2013-05-07T08:55:23.877Z
@Suresh: I appreciate the input (I was unaware of generalized Voronoi diagrams), though I don't see how, or if, this can be adapted to the case $p=1$, which is my primary concern. I suspect that a faster algorithm is possible for the case $p=1$ than for general $p$, as well.
Eric Tressler
<ds.algorithms><reference-request><cg.comp-geom>
A generalization of the geometric closest pair problem to balls
Eric Tressler
# A generalization of the geometric closest pair problem to balls

(Asked by: username_0 on 2013-05-06)

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](http://en.wikipedia.org/wiki/Closest_pair_of_points_problem)).

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

**Tags:** ds.algorithms, reference-request, cg.comp-geom
> **Comments:**
> **username_1**: If two balls have overlapping interiors, is their distance negative or zero?  
> **username_0**: 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.  
> **username_2**: The case of $p=2$ is easy because you can construct the resulting Voronoi diagram and scan the edges to find the closest pair.  
> **username_3**: @SureshVenkat: How do you take into account the radius of the balls in the Voronoi Diagram?  
> **username_2**: it's a generalized voronoi diagram that becomes the lower envelope of cones that are lowered below the plane depending on the ball radius  
> **username_0**: @Suresh: I appreciate the input (I was unaware of generalized Voronoi diagrams), though I don't see how, or if, this can be adapted to the case $p=1$, which is my primary concern. I suspect that a faster algorithm is possible for the case $p=1$ than for general $p$, as well.  

---

## 1 answers

### Answer by username_1 on 2013-05-07. Score: 3 | Accepted answer

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


---

