Question

5. (570/470 bonus) Design an algorithm whose input is a list of n points, (xu, ) for isks n. Your algorithm should run in O(n) time and determine whether or not the convex hull of these n points is a triangle. Also explain why your algorithm runs in O(n) time.

Answer 1

The main observation pertinent to designing this algorithm is that, as the convex hull requires at least three points, if the convex hull has to be a triangle, then there is a fixed choice of points that can be the vertices of the hull.

Consider the point with the smallest y coordinate. If there are multiple, choose the one with the smallest x coordinate. Denote this by . This point must be a vertex for the convex hull.
The reason for this is simple. If this point is not a vertex, then it must be generated by a convex combination of the vertices. But, any other vertex either has a higher x coordinate or a higher y coordinate. Thus, we derive a contradiction.
Note that this can be carried out in O(n) time.

Now, for each point , do the following. Calculate the angle the vector from to makes with the horizontal ray going outwards in the positive-x direction. Choose the two points which have the highest and the lowest angle. If there are multiple points for either the highest or the lowest angle, choose the ones with the highest distance.
The newly chosen points now are the candidate vertices for the triangle convex hull. As argued earlier, say the point with the maximum angle is not a vertex. Then any other point will have angle lower than it, thus the angle made by any point which is a convex combination will have angle lower than the maximum. This is a contradiction. Similar argument proves this for the point with the smallest angle.
Note that this can also be done in O(n) time.

Finally, all that remains to check is that all the points belong to the convex hull of the three chosen points. This is equivalent to checking whether a point lies in the interior of a triangle. This is easy to check.
Let be the vertices of the triangle and is the vertex to check. Consider the equation of the line joining . Let this be . Substitute the coordinates for $v_3$ and into the LHS of this equation and check if they give the same sign. If yes, do this for the other two pairs and . If all three checks succeed, the point is in the interior, otherwise not.
Again, this step takes O(n) time.

This completes the algorithm. Comment in case of any doubts.