<p>There is a randomized linear expected time algorithm by Rabin; see e.g. <a href="http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/"><em>Rabin Flips a Coin</em></a> on Lipton's blog.</p>

CC BY-SA 3.0
2012-01-20T17:41:48.763Z
2012-01-20T18:33:47.200Z
2012-01-20T18:33:47.200Z
David Eppstein
<p>As much as I understand question 2, Rabin's algorithm provides a kind of an answer to that too. At each time step the data structure is a grid with cell width less than the smallest distance between pairs of points seen so far, divided by $\sqrt{2}$ (so that no cell contains more than a single point). To answer the query in question 2, you only need to map $p$ to a cell in the grid and look at a constant number of cells around it. By the analysis of the algorithm, if the input point set is examined in random order, than the amortized update time for the grid is $O(1)$ per new point in expectation.</p>

CC BY-SA 3.0
2012-01-25T04:23:26.097Z
BTW I am referring not to the version of the algorithm as Lipton describes it, but as it is described in the first comment (and the Kleinberg and Tardos book).
Sasho Nikolov
CC BY-SA 3.0
2012-01-25T12:03:06.343Z
Only in expectation, see domotorps answer.
Raphael
CC BY-SA 3.0
2012-01-25T19:05:13.940Z
i don't see anywhere that you wanted to restrict yourself to deterministic algorithms. rabin's algorithm is interesting precisely because it goes around the decision tree lower bounds (this is similar to lower bounds for comparison sort vs. integer sorting algorithms). btw, there is probably more that rabin uses to go around the lower bound, namely the hashing trick used to access the grid
Sasho Nikolov
CC BY-SA 3.0
2012-01-25T19:54:24.890Z
Re the "more that Rabin uses": also the ability to round real-number inputs to integers. One needs to be very careful with this: if you set up a model of computation in which one can do standard arithmetic operations and rounding on real numbers, all in constant time per operation, then it's possible to solve PSPACE-complete problems in polynomial time in this model. But Rabin only rounds input numbers (to different levels of precision in different iterations), and this circumscribed form of rounding isn't problematic.
David Eppstein
CC BY-SA 3.0
2012-01-26T09:10:41.013Z
@SashoNikolov I was looking for *worst-case* time in $o(n \log n)$, so also *worst-case* $O(1)$ in question 2. This has nothing to do with wether the algorithm is deterministic. I am not sure what happens if you combine expected and amortised time.
Raphael
CC BY-SA 3.0
2012-01-26T18:05:08.857Z
@DavidEppstein great clarification, thanks! Raphael, your comment above says that your problem is the expected time, but apparently you meant that your problem is the amortized analysis. Maybe you want to change your question, because right now it says "amortized $O(1)$".
Sasho Nikolov
CC BY-SA 3.0
2012-01-25T04:13:44.270Z
2012-01-25T04:13:44.270Z
Sasho Nikolov
<p>It is impossible to solve the problem in less than $cn\log n$ time in standard models, e.g. using algebraic decision trees. This follows from the work of Yao and Ben-Or that shows that in this model it is not possible to decide if a set of $n$ input numbers are all different or not (see <a href="http://people.bath.ac.uk/masnnv/Teaching/AAlg11_8.pdf">http://people.bath.ac.uk/masnnv/Teaching/AAlg11_8.pdf</a>). In case of your problem, imagine that all of them are on the real line. If two points are the same, then your output would be two points with distance zero, while otherwise not, so a solution to your problem would also solve the DISTINCT NUMBERS problem. If you want to suppose that all your points are different, then just add $i\epsilon$ to the $x_i$ inputs of the DISTINCT NUMBERS problem, in this case if your output is at most $n\epsilon$, then the numbers are not all distinct. (Although in this case you have to use a promise version where the difference of any two distinct numbers is at least $2n\epsilon$, but I think the same proof works to show that you also need $\Omega(n\log n)$ in this case.)</p>

CC BY-SA 3.0
2012-01-25T12:02:41.663Z
Indeed, thanks. That answers question 2 (negatively), too.
Raphael
CC BY-SA 3.0
2012-01-25T17:53:50.670Z
The problem you mention is apparently also known as [Element Distinctness Problem](http://en.wikipedia.org./wiki/Element_distinctness_problem).
Raphael
CC BY-SA 3.0
2012-02-13T23:19:55.300Z
@Sariel Har-Peled's reference (http://goo.gl/pLiEO) presents a practical linear-time algorithm for finding the closest pair.  That document directly addresses this argument, and explains that it does not apply because the algorithm uses a more powerful computation model.
kevin cline
CC BY-SA 3.0
2012-02-14T04:30:43.893Z
Yes, but the question specifically asked for worst case running time. But I agree that all my observations appear already in Sariel's thesis.
domotorp
CC BY-SA 3.0
2012-01-25T06:00:19.580Z
2012-01-25T07:40:39.917Z
2012-01-25T07:40:39.917Z
domotorp
<p>The following exercise has been handed out to students I supervise:</p>

<blockquote>
  <p>Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of points. The algorithm should run in time $o(n^2)$.</p>
</blockquote>

<p>There is a (relatively) simple divide and conquer algorithm that solves the task in time $\Theta(n \log n)$.</p>

<p><strong>Question 1</strong>: Is there an algorithm that solves the given problem exactly in worst-case time $\mathcal{o}(n \log n)$?</p>

<p>What made me suspect  that this might be possible is a result I remember to have seen in some talk (reference appreciated). It stated something along the lines of that not more than a constant number $c \in \mathbb{N}$ of points can be arranged in the plane around some point $p$ inside a circle of radius $r \in \mathbb{R}$, with $r$ the minimal distance between any two of the involved points. I think $c=7$, the points forming a equilateral hexagon with $p$ in the center (in the extreme case).</p>

<p>In that case, the following algorithm should solve them problem in $n$ steps.</p>

<pre><code>fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end
</code></pre>

<p>Note that this is (claimed to be) in linear time because only a constant number of points in <code>r</code> can be no farer away than <code>m</code> from <code>p</code> (assuming above statement); only these points have to be investigated for finding a new minimum. There is a catch, of course; how do you implement <code>nextNeighbour</code> (maybe with preprocessing in linear time)?</p>

<p><strong>Question 2</strong>: Let a set of points $R$ and a point $p \notin R$. Let $m \in \mathbb{R}$ with </p>

<p>$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$ </p>

<p>and </p>

<p>$\qquad R_{p,m} := \{p&#39; \mid p&#39; \in R \wedge \mathrm{dist}(p, p&#39;) \leq m\}$.</p>

<p>Assume $R_{p,m}$ is finite. Is it possible to find $p&#39; \in R_{p,m}$ with minimal distance from $p$ in (amortised) time $\mathcal{O}(1)$? (You may assume $R$ to be constructed by adding investigated points $p$ one by one.)</p>

CC BY-SA 3.0
2012-01-20T15:32:37.960Z
I'd propose to search with "closest pair" as a keyword.
Yoshio Okamoto
CC BY-SA 3.0
2012-01-22T00:11:54.303Z
This is all standard stuff by now, see first two chapters here: http://goo.gl/pLiEO
Sariel Har-Peled
CC BY-SA 3.0
2012-01-22T02:51:25.143Z
Ps. If you want expected time, then you can even compute the Delaunay triangulation, which contains the minimum distance.
domotorp
CC BY-SA 3.0
2012-01-22T08:53:10.450Z
After question 1 you write "not more than a constant number of points can be arranged in the plane around some point p inside a circle of radius r, with r the minimal distance between p and any other point." This is certainly not true: You can take any number of points on the circle of radius r. Your statement is true if r is the minimal distance between any two points, in which case the proof is quite simple.
domotorp
CC BY-SA 3.0
2012-01-23T05:40:41.357Z
the first question is textbook stuff, as already pointed out: definitely not research level. i do not understand the second question: for any $m$, the $p'$ you are asking for either doesn't exist or is the closest neighbor to $p$ in $R$. so how is this different from question 1? what are you amortizing over (i.e. if this is a data structure question what are the updates and queries)?
Sasho Nikolov
CC BY-SA 3.0
2012-01-23T10:32:25.030Z
@SarielHar-Peled Although the focus of this book (approximation) does not fit the question at all, I appreciate the chapter about quadtrees. Thanks!
Raphael
CC BY-SA 3.0
2012-01-23T10:55:17.973Z
@SashoNikolov Right, the question contained the same bug domotorp pointed out. I hope I could correct/clarify it now. If the answer to Q2 is "yes" then Q1 can be answered "yes", too. The reverse is not necessarily true. Amortising should happen along the lines of `mindist` (or similar), although management of set $R$ is implicit there.
Raphael
<ds.data-structures><cg.comp-geom>
Find Shortest Pairwise Distance of Points in o(n log n)?
Raphael
# Find Shortest Pairwise Distance of Points in o(n log n)?

(Asked by: username_0 on 2012-01-20)

The following exercise has been handed out to students I supervise:

Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of points. The algorithm should run in time $o(n^2)$.

There is a (relatively) simple divide and conquer algorithm that solves the task in time $\Theta(n \log n)$.
Question 1: Is there an algorithm that solves the given problem exactly in worst-case time $\mathcal{o}(n \log n)$?
What made me suspect  that this might be possible is a result I remember to have seen in some talk (reference appreciated). It stated something along the lines of that not more than a constant number $c \in \mathbb{N}$ of points can be arranged in the plane around some point $p$ inside a circle of radius $r \in \mathbb{R}$, with $r$ the minimal distance between any two of the involved points. I think $c=7$, the points forming a equilateral hexagon with $p$ in the center (in the extreme case).
In that case, the following algorithm should solve them problem in $n$ steps.
fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Note that this is (claimed to be) in linear time because only a constant number of points in r can be no farer away than m from p (assuming above statement); only these points have to be investigated for finding a new minimum. There is a catch, of course; how do you implement nextNeighbour (maybe with preprocessing in linear time)?
Question 2: Let a set of points $R$ and a point $p \notin R$. Let $m \in \mathbb{R}$ with 
$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$ 
and 
$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$.
Assume $R_{p,m}$ is finite. Is it possible to find $p' \in R_{p,m}$ with minimal distance from $p$ in (amortised) time $\mathcal{O}(1)$? (You may assume $R$ to be constructed by adding investigated points $p$ one by one.)

**Tags:** ds.data-structures, cg.comp-geom
> **Comments:**
> **username_1**: I'd propose to search with "closest pair" as a keyword.  
> **username_2**: This is all standard stuff by now, see first two chapters here: http://goo.gl/pLiEO  
> **username_3**: Ps. If you want expected time, then you can even compute the Delaunay triangulation, which contains the minimum distance.  
> **username_3**: After question 1 you write "not more than a constant number of points can be arranged in the plane around some point p inside a circle of radius r, with r the minimal distance between p and any other point." This is certainly not true: You can take any number of points on the circle of radius r. Your statement is true if r is the minimal distance between any two points, in which case the proof is quite simple.  
> **username_4**: the first question is textbook stuff, as already pointed out: definitely not research level. i do not understand the second question: for any $m$, the $p'$ you are asking for either doesn't exist or is the closest neighbor to $p$ in $R$. so how is this different from question 1? what are you amortizing over (i.e. if this is a data structure question what are the updates and queries)?  
> **username_0**: @SarielHar-Peled Although the focus of this book (approximation) does not fit the question at all, I appreciate the chapter about quadtrees. Thanks!  
> **username_0**: @SashoNikolov Right, the question contained the same bug domotorp pointed out. I hope I could correct/clarify it now. If the answer to Q2 is "yes" then Q1 can be answered "yes", too. The reverse is not necessarily true. Amortising should happen along the lines of `mindist` (or similar), although management of set $R$ is implicit there.  

---

## 3 answers

### Answer by username_3 on 2012-01-25. Score: 12 | Accepted answer

It is impossible to solve the problem in less than $cn\log n$ time in standard models, e.g. using algebraic decision trees. This follows from the work of Yao and Ben-Or that shows that in this model it is not possible to decide if a set of $n$ input numbers are all different or not (see <http://people.bath.ac.uk/masnnv/Teaching/AAlg11_8.pdf>). In case of your problem, imagine that all of them are on the real line. If two points are the same, then your output would be two points with distance zero, while otherwise not, so a solution to your problem would also solve the DISTINCT NUMBERS problem. If you want to suppose that all your points are different, then just add $i\epsilon$ to the $x\_i$ inputs of the DISTINCT NUMBERS problem, in this case if your output is at most $n\epsilon$, then the numbers are not all distinct. (Although in this case you have to use a promise version where the difference of any two distinct numbers is at least $2n\epsilon$, but I think the same proof works to show that you also need $\Omega(n\log n)$ in this case.)

> **Comments:**
> **username_0**: Indeed, thanks. That answers question 2 (negatively), too.  
> **username_0**: The problem you mention is apparently also known as [Element Distinctness Problem](http://en.wikipedia.org./wiki/Element_distinctness_problem).  
> **username_6**: @Sariel Har-Peled's reference (http://goo.gl/pLiEO) presents a practical linear-time algorithm for finding the closest pair.  That document directly addresses this argument, and explains that it does not apply because the algorithm uses a more powerful computation model.  
> **username_3**: Yes, but the question specifically asked for worst case running time. But I agree that all my observations appear already in Sariel's thesis.  

---

### Answer by username_5 on 2012-01-20. Score: 17

There is a randomized linear expected time algorithm by Rabin; see e.g. [*Rabin Flips a Coin*](http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/) on Lipton's blog.


---

### Answer by username_4 on 2012-01-25. Score: 0

As much as I understand question 2, Rabin's algorithm provides a kind of an answer to that too. At each time step the data structure is a grid with cell width less than the smallest distance between pairs of points seen so far, divided by $\sqrt{2}$ (so that no cell contains more than a single point). To answer the query in question 2, you only need to map $p$ to a cell in the grid and look at a constant number of cells around it. By the analysis of the algorithm, if the input point set is examined in random order, than the amortized update time for the grid is $O(1)$ per new point in expectation.

> **Comments:**
> **username_4**: BTW I am referring not to the version of the algorithm as Lipton describes it, but as it is described in the first comment (and the Kleinberg and Tardos book).  
> **username_0**: Only in expectation, see domotorps answer.  
> **username_4**: i don't see anywhere that you wanted to restrict yourself to deterministic algorithms. rabin's algorithm is interesting precisely because it goes around the decision tree lower bounds (this is similar to lower bounds for comparison sort vs. integer sorting algorithms). btw, there is probably more that rabin uses to go around the lower bound, namely the hashing trick used to access the grid  
> **username_5**: Re the "more that Rabin uses": also the ability to round real-number inputs to integers. One needs to be very careful with this: if you set up a model of computation in which one can do standard arithmetic operations and rounding on real numbers, all in constant time per operation, then it's possible to solve PSPACE-complete problems in polynomial time in this model. But Rabin only rounds input numbers (to different levels of precision in different iterations), and this circumscribed form of rounding isn't problematic.  
> **username_0**: @SashoNikolov I was looking for *worst-case* time in $o(n \log n)$, so also *worst-case* $O(1)$ in question 2. This has nothing to do with wether the algorithm is deterministic. I am not sure what happens if you combine expected and amortised time.  
> **username_4**: @DavidEppstein great clarification, thanks! Raphael, your comment above says that your problem is the expected time, but apparently you meant that your problem is the amortized analysis. Maybe you want to change your question, because right now it says "amortized $O(1)$".  

---

