How to find largest triangle in convex hull aside from brute force search

Yes, you can do significantly better than brute-force.

By brute-force I assume you mean checking all triples of points, and picking the one with maximum area. This runs in O(n³) time, but it turns out that it is possible to do it in not just O(n²) but in O(n) time!

[Update: A paper published in 2017 showed by example that the O(n) solution doesn’t work for a specific class of polygons. See this answer for more details. But the O(n²) algorithm is still correct.]

By first sorting the points / computing the convex hull (in O(n log n) time) if necessary, we can assume we have the convex polygon/hull with the points cyclically sorted in the order they appear in the polygon. Call the points 1, 2, 3, … , n. Let (variable) points A, B, and C, start as 1, 2, and 3 respectively (in the cyclic order). We will move A, B, C until ABC is the maximum-area triangle. (The idea is similar to the rotating calipers method, as used when computing the diameter (farthest pair).)

With A and B fixed, advance C (e.g. initially, with A=1, B=2, C is advanced through C=3, C=4, …) as long as the area of the triangle increases, i.e., as long as Area(A,B,C) ≤ Area(A,B,C+1). This point C will be the one that maximizes Area(ABC) for those fixed A and B. (In other words, the function Area(ABC) is unimodal as a function of C.)

Next, advance B (without changing A and C) if that increases the area. If so, again advance C as above. Then advance B again if possible, etc. This will give the maximum area triangle with A as one of the vertices.

(The part up to here should be easy to prove, and simply doing this separately for each A would give an O(n²) algorithm.)

Now advance A again, if it improves the area, and so on._{(The correctness of this part is more subtle: Dobkin and Snyder gave a proof in their paper, but a recent paper shows a counterexample. I have not understood it yet.)}

Although this has three “nested” loops, note that B and C always advance “forward”, and they advance at most 2n times in total (similarly A advances at most n times), so the whole thing runs in O(n) time.

Code fragment, in Python (translation to C should be straightforward):

 # Assume points have been sorted already, as 0...(n-1)
 A = 0; B = 1; C = 2
 bA= A; bB= B; bC= C #The "best" triple of points
 while True: #loop A

   while True: #loop B
     while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
       C = (C+1)%n
     if area(A, B, C) <= area(A, (B+1)%n, C): 
       B = (B+1)%n
       continue
     else:
       break

   if area(A, B, C) > area(bA, bB, bC):
     bA = A; bB = B; bC = C

   A = (A+1)%n
   B = (A+1)%n
   C = (A+2)%n
   if A==0: break

This algorithm is proved in Dobkin and Snyder, On a general method for maximizing and minimizing among certain geometric problems, FOCS 1979, and the code above is a direct translation of their ALGOL-60 code. Apologies for the while-if-break constructions; it ought to be possible to transform them into simpler while loops.

More Related Contents:

Leave a Comment Cancel reply