2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ I think the convex hull can be explained by using the fact that the longest line segment which can be drawn inside a triangle is from vertex to vertex. Then you show that any diagonal can be enclosed by $3$ points of the convex hull ('enclosed' also counting the cases where the diagonal is part of an edge in this case). $\endgroup$
    – Shuri2060
    Jul 14, 2017 at 14:03
  • $\begingroup$ Does a side (such as the base of a trapezium) count as a "diagonal" here? $\endgroup$ Jul 14, 2017 at 14:07
  • $\begingroup$ @HenningMakholm Yes, it does $\endgroup$
    – Ctx
    Jul 14, 2017 at 14:08

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you, that sounds good! Is there an explanation on why this works? Another constraint is, that all longest diagonals have to be found, will this also be the case when keeping all diagonals of the same (maximum) length while walking around the convex hull as you described only a single time? $\endgroup$
    – Ctx
    Jul 14, 2017 at 14:20
  • $\begingroup$ @Ctx: on further thought, it does't necessarily work. Back to the drawing board ... $\endgroup$ Jul 14, 2017 at 14:21
  • $\begingroup$ Np, but it is certainly a good starting point for thinking! $\endgroup$
    – Ctx
    Jul 14, 2017 at 14:22
0
$\begingroup$

There is a linear algorithm called "Rotating Calipers" found by Shamos in his 1978 thesis.

I think you are going to find Solving Geometric Problems with the Rotating Calipers by G. Toussaint enlightening.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .