Closest group of 3 points

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.

There is an obvious algorithm which works in O(n^2).

1) perform Delaunay triangluation - O(n log n), so we get a planar graph.

As it is Delaunay triangluation, which maximises the minimum angle, it is clear that the closest 3 points must be connected by at least 2 edges (but they don't necessarily need to form the triangle!). Otherwise there would be more closer points or more closed angles.

2) for each point (vertex of the graph), we examine each couple of adjacent edges and look the 3 vertices defined by these 2 edges.

How much time will the step 2) will take? Since the graph is planar, the number of edges is <= 3n - 6, i.e. O(n). So this step will take O(n^2) in the worst case (O(n) in the typical case, where the degree of each vertex is limited).

So the whole algorithm is O(n^2). Note that the step 2) is somehow naive (brute force) solution, so I think there is a space for improvement (also, the steps 1 and 2 could probably be merged somehow).