CODEWITHSUNDEEP
mathgraphgraph-theory
Tyler Murry
Tyler Murry

Reputation: 2815

Next Closest Pair Problem

I'm sure most are familiar with the closest pair problem, but is there another alogrithm or a way to modify the current CP algorithm to get the next closest pair?

Upvotes: 1

Views: 429

Answers (2)

Ante
Ante

Reputation: 5458

If constant number of minimal distances (next pairs) are needed, it is possible to modify steps 3-5, from Wikipedia article, redefining d_Lmin, d_Rmin, d_LRmin as constant length lists of minimum distances. That uses c*log(n) memory.

If next is used less than O(n) times, than reformulation of CR problem to return smaller distance larger than given d is same as next method. It can be implemeted with same approach as CR. I don't see theoretical guaranty that step 4 can be accomplished in linear time, but there is advantage not to check points in to small boxes.

If next is used more than O(n) times, than it is the best to calculate all distances and sort them (if memory is not a problem).

Upvotes: 0

Loïc Février
Loïc Février

Reputation: 7750

Easy one, in O(n log(n)) :

  • find the closets pair (p1,p2) in O(n log(n))
  • compute all pairs with p1 or p2 (but not (p1,p2)) keep the closest one, let's call it E in O(n)
  • remove p1 and p2 in (1)
  • find the closets pair, compare it to E and keep the closest one, again in O(n log(n))

You now have the second closest one.

Upvotes: 1

Related Questions