I am trying to find an efficient and elegant solution to find all of the longest diagonals of a (general) polygon.
I assume, that all end points of those diagonals have to be on the border of the convex hull, so the rest of the points may be discarded. Is this correct? I have some difficulty to prove this, but it feels right.
Then, the naive approach is to calculate all lengths of all diagonals of the remaining points and keep the longest ones. This is O(n²), with n being the number of the polygons end points on the border of the convex hull.
Is there a more sophisticated solution for this problem?
Best Answer
Yes, it is enough to consider the convex hull. Suppose $PQ$ is a longest diagonal. Then all of the points must be within a circle through $Q$ centered on $P$. But this means that $Q$ cannot possibly be a convex combination of other points, so $Q$ is a corner of the convex hull. Likewise for $P$, of course.
Once you compute the convex hull (which can be done in $O(n\log n)$ time), assume WLOG that the polygon is convex.
Then just a small bit of ingenuity lets you find the longest diagonal in linear additional time: Choose one corner $a$ and find (in linear time) the corner $b$ that is farthest from it. Move $a$ clockwise around the polygon, and while you're doing that, step $b$ clockwise too whenever that moves it away from $a$.This procedure will produce the longest diagonal from each $a$, and therefore also the longest diagonal all in all.Oops... this doesn't necessarily work. The distance from a fixed point $a$ to $b$ somewhere else on the perimeter can have a local maximum that is not global.