How to find minimal and maximal angle determined by three points selected from n points?

Question

Given n points in 2-D plane, like (0,0),(1,1), ... We can select any three points from them to construct angle. For example, we choose A(0, 0), B(1, 1), C(1, 0), then we get angle ABC = 45 degree, ACB = 90 degree and CAB = 45 degree.

My question is how to calculate max or min angle determined by three points selected from n points.

Obviously, we can use brute-force algorithm - calculate all angels and find maximal and minimal value, using Law Of Cosines to calculate angles and Pythagorean theorem to calculate distances. But does efficient algorithm exist?

Answer 1

If I'm correct, brute-force runs in O(n^3): you basically take every triplet, compute the 3 angles, and store the overall max.

You can improve slightly to O(n^2 * log(n)) but it's trickier:

best_angle = 0
for each point p1:
    for each point p2:
        compute vector (p1, p2), and the signed angle it makes with the X-axis
        store it in  an array A
    sort array A    # O(n * log(n))
    # Traverse A to find the best choice:
    for each alpha in A:
         look for the element beta in A closest to alpha+Pi 
         # Takes O(log n) because it's sorted. Don't forget to take into account the fact that A represents a circle: both ends touch...
        best_angle = max(best_angle, abs(beta - alpha))

The complexity is O(n * (n + nlog(n) + n * log(n))) = O(n^2 * log(n))

Of course you can also retrieve the pt1, pt2 that obtained the best angle during the loops.

There is probably still better, this feels like doing too much work overall, even if you re-use your previous computations of pt1 for pt2, ..., ptn ...