10
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I'd propose to search with "closest pair" as a keyword. $\endgroup$
    – Yoshio Okamoto
    Jan 20, 2012 at 15:32
  • $\begingroup$ This is all standard stuff by now, see first two chapters here: goo.gl/pLiEO $\endgroup$
    – Sariel Har-Peled
    Jan 22, 2012 at 0:11
  • $\begingroup$ Ps. If you want expected time, then you can even compute the Delaunay triangulation, which contains the minimum distance. $\endgroup$
    – domotorp
    Jan 22, 2012 at 2:51
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Jan 22, 2012 at 8:53
  • $\begingroup$ 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)? $\endgroup$
    – Sasho Nikolov
    Jan 23, 2012 at 5:40

3 Answers 3

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Indeed, thanks. That answers question 2 (negatively), too. $\endgroup$
    – Raphael
    Jan 25, 2012 at 12:02
  • $\begingroup$ The problem you mention is apparently also known as Element Distinctness Problem. $\endgroup$
    – Raphael
    Jan 25, 2012 at 17:53
  • $\begingroup$ @Sariel Har-Peled's reference (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. $\endgroup$
    – kevin cline
    Feb 13, 2012 at 23:19
  • 1
    $\begingroup$ Yes, but the question specifically asked for worst case running time. But I agree that all my observations appear already in Sariel's thesis. $\endgroup$
    – domotorp
    Feb 14, 2012 at 4:30
17
$\begingroup$

There is a randomized linear expected time algorithm by Rabin; see e.g. Rabin Flips a Coin on Lipton's blog.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$
    – Sasho Nikolov
    Jan 25, 2012 at 4:23
  • $\begingroup$ Only in expectation, see domotorps answer. $\endgroup$
    – Raphael
    Jan 25, 2012 at 12:03
  • $\begingroup$ 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 $\endgroup$
    – Sasho Nikolov
    Jan 25, 2012 at 19:05
  • 4
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Jan 25, 2012 at 19:54
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Jan 26, 2012 at 9:10

Your Answer

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

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