- #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 :)

- 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,916

- 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

- Last Post

- Replies
- 21

- Views
- 4K

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 3K

- Last Post

- Replies
- 7

- Views
- 3K

- Replies
- 3

- Views
- 5K

- Replies
- 4

- Views
- 553

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 1K