- #1

- 5

- 0

There are N points on a plane. Find the two points that are closest, in time better than O(N^2).

Any idea?

Thanks :)

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Atlas
- Start date

- #1

- 5

- 0

There are N points on a plane. Find the two points that are closest, in time better than O(N^2).

Any idea?

Thanks :)

- #2

- 379

- 0

randomly pick point p. then choose point P+1....

- #3

AKG

Science Advisor

Homework Helper

- 2,565

- 4

- #4

- 5

- 0

- #5

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

If the problem was "Given an arbitrary function f(P, Q) of two points, find the pair of points that minimizes f(P, Q)", can you prove that the best algorithm is Θ(n²)?

- #6

- 5

- 0

Found a solution here:

http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

Share: