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

Question

Given a convex polygon, how do I find the 3 points that define a triangle with the greatest area.

Related: Is it true that the circumcircle of that triangle would also define the minimum bounding circle of the polygon?

Answer 1

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    if A==B: B = (B+1)%n    if B==C: C = (C+1)%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.

Answer 2

According to this paper, there is a class of convex polygons in which the algorithm cited by ShreevatsaR's answer fails. The paper also proposes a O(n log n) divide and conquer algorithm for solving the problem.

Apparently, the simpler O(n²) algorithm in which you move points B and C for all A is still valid.