Closest group of 3 points

Question

Is there a known, efficient algorithm for finding the closest group of three points in a cloud?

This is similar to the closest pair of points problem but I am looking for three points instead of two.

---

Edit
The definition of "closest" will affect the complexity of the algorithm. As Jack pointed out, finding the minimum area triangle is 3sum-hard and in any case not well suited to my application.

I am hoping there is a more efficient algorithm for finding the minimum perimiter (i.e. |AB|+|AC|+|BC|) triangle or something similar (e.g. minimum |AB|²+|AC|²+|BC|².) I know of no reason why this should be 3sum-hard as the existence of 3 colinear points elsewhere would not affect the result.

---

Note: my points have eight dimensions, so any algorithm that is restricted to fewer dimensions is not suitable.

Answer 1

This problem is similar to the classical problem of finding the closest pair in a set of points. You can adapt the worst-case O(n log n) algorithms that solve the closest-pair problem to solve this one.

The specific problem was featured in Google's Code Jam competition. Here is a resume of the analysis:

The number of points can be pretty large so we need an efficient algorithm. We can solve the problem in O(n log n) time using divide and conquer. We will split the set of points by a vertical line into two sets of equal size. There are now three cases for the minimum-perimeter triangle: its three points can either be entirely in the left set, entirely in the right set, or it can use points from each half.

Further:

"To find the minimum perimeter for the third case (if it is less than p)":

1. We select the points that are within a distance of p/2 from the vertical separation line.
2. Then we iterate through those points from top to bottom, and maintain a list of all the points in a box of size p x p/2, with the bottom edge of the box at the most recently considered point.
3. As we add each point to the box, we compute the perimeter of all triangles using that point and each pair of points in the box. (We could exclude triangles entirely to the left or right of the dividing line, since those have already been considered.)

We can prove that the number of points in the box is at most 16, so we only need to consider at most a small constant number of triangles for each point.

It seems to me you could even adapt the method to work in the |AB|²+|AC|²+|BC|² case.