CODEWITHSUNDEEP
algorithmcomputational-geometrydivide-and-conquer
user3708915
user3708915

Reputation: 341

finding 3 closest points on a plane

We know the fast algorithm to find the 2 closest points is using divide and conquer. The solution of that is here http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

Now here is a upgrade of this problem. For any three points, pi, pj , and pk, the three-distance td(p1, p2, p3) of these points be the sum of the two smaller of distance among dist(p1,p2),dist(p2,p3)and dist(p1,p3).

What is the efficient way to find out the smallest three-distance of all possible 3 points combination on the plane?

Upvotes: 1

Views: 2580

Answers (2)

Derek Illchuk
Derek Illchuk

Reputation: 5658

My implementation is here - Closest Triplet; I think it's worth a look.

Whether there were any challenges to convert from Closest Pair, I don't recall. It doesn't look like it.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65458

To recap the divide-and-conquer algorithm for closest pair: bisect the n points vertically into n/2 and n/2. Find the closest pair in each half. Let d be the distance between the closest intra-half pair. Slide a box of radius O(d) down the bisection line, considering inter-half pairs where both points lie in the box.

An O(n log n)-time divide-and-conquer algorithm for the 3-point combination problem isn't going to be very different at all. The core of the argument for pairs is that the box contains O(1) points at all times, so it's no problem to iterate over triples instead; the merge step still will be linear-time. The ad hoc density argument ("six points") has to be replaced, but I'm loath to give details on the off chance that this is homework, since it's really only needed for the analysis and not the implementation.

Upvotes: 3

Related Questions