Largest triangle in convex hull

Question

The question has already been answered, but the main problem I am facing is in understanding one of the answers..

From https://stackoverflow.com/a/1621913/2673063

How is the following algorithm O(n) ?

It states as 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 O(n2). But read on.) Now advance A again, if it improves the area, etc. 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.

Answer 1

As the author of the answer that is the subject of the question, I feel obliged to give a more detailed explanation of the O(n) runtime.

---

Firstly, just as an example, here is a figure from the paper, showing the first few steps of the algorithm, for a particular sample input (a 12-gon). First we start with A, B, C as three consecutive vertices (step 1 in the figure), advance C as long as area increases (steps 2 to 6), then advance B, and so on.

The triangles with asterisks above them are the "anchored local maxima", i.e., the ones that are best for a given A (i.e., advancing either C or B would decrease the area).

---

As far as the runtime being O(n): Let the "actual" value of B, in terms of the number of times it's been incremented and ignoring the wrap around, be nB, and similarly for C be nC. (In other words, B = nB % n and C = nC % n.) Now, note that,

1. ("B is ahead of A") whatever the value of A, we have A ≤ nB < A + n

2. nB is always increasing

So, as A varies from 0 to n, we know that nB only varies between 0 and 2n: it can be incremented at most 2n times. Similarly nC. This shows that the running time of the algorithm, which is proportional to the total number of times A, B and C are incremented, is bounded by O(n) + O(2n) + O(2n), which is O(n).

Answer 2

Think about it like this: each of A, B, C are pointers that, at any given moment, point towards one of the elements of the convex hull. Due to the way the algorithm increments them, each one of them will point to each element of the convex hull at most once. Therefore, each one will iterate over a collection of O(n) elements. They will never be reset, once one of them has passed an element, it will not pass that element ever again.

Since there are 3 pointers (A, B, C), we have time complexity 3 * O(n) = O(n).

Edit:

As the code is presented in the provided link, it sounds possible that it is not O(n), since B and C wrap around the array. However, according to the description, this wrapping around does not sound necessary: before seeing the code, I imagined the method stopping the advancement of B and C past n. In that case, it would definitely be O(n). As the code is presented however, I'm not sure.

It might still be that, for some mathematical reason, B and C still iterate only O(n) times in the entirety of the algorithm, but I can't prove that. Neither can I prove that it is correct to not wrap around (as long as you take care of index out of bounds errors).