1
$\begingroup$

I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78.

It reads

Consult Figure 3.23 and notice that parallel lines of support cannot be made to pass through every pair of points. For example, no lines of support through vertices $D$ and $F$ can be parallel. This means that $DF$ is not a diameter. A pair of points that does admit parallel supporting lines will be called antipodal.

non-antipodal

Problem: How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

My Informal Attempt: See Figure 3.23. Intuitively, by rotating the line $DC$ about $C$ and then $CB$ about $B$, we can get two parallel lines of support passing through $F$ and $B$. However, is $FB$ necessarily longer than $FD$? If so, how to prove it?


A line $L$ is a line of support of a convex polygon $P$ if it meets the boundary of $P$ and $P$ lies entirely on one side of $L$. (Definition 3.6; Page 69)

$\endgroup$
  • $\begingroup$ Your definition of line of support sounds a bit strange. Do you mean that such a line intersects the boundary of P, but not the interior? Also, what is the definition of a diameter of an arbitrary polygon? $\endgroup$ – Discrete lizard Mar 16 '18 at 14:17
  • $\begingroup$ @Discretelizard (1) Yes, it intersects the boundary of $P$, but not the interior. (2) It is a convex polygon. The diameter of a convex polygon $P$ is the maximal length of a pair of points of $P$. $\endgroup$ – hengxin Mar 16 '18 at 14:57
  • $\begingroup$ Your informal attempt seems to try to prove the converse of your statement, i.e. 'any segment between a pair of anti-podal points is a diameter'. This is statement is false. Take a (non-diamond) kite, for instance. Both opposing points are anti-podal, but it is clear that the segment between only one of them is a diameter. Hmm, wait, this should be part of my answer $\endgroup$ – Discrete lizard Mar 16 '18 at 16:03
1
$\begingroup$

I find it easier to prove the equivalent statement 'any pair $A,B$ such that the segment between them is a diameter of $P$ must be anti-podal':

If the segment $s$ between $A,B$ is a diameter, construct the lines $k,l$ as follows: line $l$ is the unique line perpendicular to $s$ and through $A$. Line $k$ is the unique line perpendicular to $s$ and through $B$.

I claim that the lines $l,k$ are parallel lines of support. These lines are parallel, as they are perpendicular to the same segment. To see that they are lines of support, suppose to the contrary that $l$ is not a line of support. As $A$ lies on the boundary of $P$ and in $l$, $l$ intersects the boundary of $P$. So $l$ can only not be a line of support if it intersects the interior of $P$. But this means that there is a point $X$ in $P$ ('beyond' the line $l$) such that $|XB|>|AB|$, contradicting the fact that $s$ is a diameter of $P$!

So $l$ is a line of support. Analogously, $k$ is a line of support as well. So, as there is a parallel pair of lines of support through $A$ and $B$, $A$ and $B$ are anti-podal.

$\square$

The picture below sketches the situation where $A,B$ are endpoints of a diameter of $P$. A position where the hypothetical point $X$ could lie is also shown (it is clear that here there can be no point $X$ such that it lies in $P$!) Note that while $C,D$ are not endpoints of a diameter, they are anti-podal!

situation sketch

Be careful though, as the converse of the statement, 'Any segment such that the endpoints $A,B$ of that segment are antipodal in $P$ is a diameter in $P$' is false. As a counterexample, take a (non-square) kite (or take the sketch above). Clearly, the two pairs of opposing corners are anti-podal, but only one of the segments between the pairs is a diameter! Your informal attempt seems to try to prove this. As what you're trying to prove is false, it isn't surprising that formalizing the proof fails!


Note that I don't use the fact that $P$ is convex. You can check that this proof also works for non-convex, but simple polygons (it might even work for non-simple polygons, but these things are awful, so I'd rather not make claims about them). Note that in the case of convexity, the diameter need not necessarily be contained within the polygon, but all definitions still apply.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.