Find the Diameter of a Convex

Problem: Give a convex that contains n vertices, find its diameter, basically the pair of vertices that have the longest distance.

Solution: This is the essential problem to solve the more general problem: find the farthest pair of points among n points, but now let's focus on this problem. Assume the vertices of the convex are ordered counter-clockwise (clockwise is also OK) and they are labeled as v1, v2, ..., vn, we can use method that mimics "rotating the convex" to solve the problem in O(n).

First we need to introduce the concept of antipodal pair, the diameter must be the distance between one antipodal pair. Therefore, if we found all antipodal pairs, we can get the diameter. Then how to find all the antipodal pairs efficiently? The detail is as follow:

1. For edge vnv1 (the line that connects vn and v1), we follow the couter-clockwise order to find the vertex that is farthest from vnv1. We name it vk.  
2. Then we move to edge v1v2, again, we try to find the vertex that is farthest from v1v2. We name it vp. It is easy to see any vertex from vk to vp form an antipodal pair with v1, then we add the pairs (v1, vk), ... , (v1, vp) to our antipodal set.
3. Then we let vk = vp  and move to edge v2v3. Again try to find the vertex that is farthest from v2v3. This vertex will be the new vp. Repeat this process until we finish processing the edge vn-1vn.
4. Now we get all the antipodal pairs, just do a linear scan to find the maximum.

When calculating distance, we can used signed area which avoids square root calculation.

More: To solve the farthest pair of points problem, basically we first first the convex hull of these points, then we apply this convex diameter algorithm. The total cost is O(nlogn) which is dominated by the cost of finding convex hull.