Welcome to NRICH.

 
How big is the smallest circle that covers a polygon?
By Graeme Mcrae on Monday, February 11, 2002 - 06:53 pm:

How can you prove that the diameter of the smallest circle that covers a polygon is smaller than (or at least no larger than) half the perimeter of the polygon?

By Arvan Pritchard on Tuesday, February 12, 2002 - 04:43 pm:

You could repeatedly delete polygon vertices provided you leave 3 on the circle. At each deletion you reduce the polygon perimeter or leave it unchanged, and if you can prove the result for the triangle you end up with you have finished.

If the original polyon has only two points on the circle they must be opposite ends of a diameter, and you can reduce to a pair of straight lines in the same way.

By Brad Rodgers on Tuesday, February 12, 2002 - 04:48 pm:

You can prove the result for a triangle fairly easily with a little deduction and Ptolemy's theorem. I'm very crunched for time now, though; I'll type more later.

Brad

By Graeme Mcrae on Tuesday, February 12, 2002 - 07:45 pm:

Brad, this is where I have trouble. If three vertices of the polynomial are on the minimum spanning circle, then how do you show that the perimeter of the triangle is at least twice the diameter of the circumscribed circle?

In general, it is not true that the perimeter of a triangle is at least twice the diameter of the circumscribed circle. Intuitively this is clear; if the angles of the triangle are, say, 1º, 1º, and 178º, the circumscribed circle is HUGE!

By Brad Rodgers on Tuesday, February 12, 2002 - 10:43 pm:

This post will still be somewhat shortwinded, but basically, the idea is that there are two distinct possibilities, either a side of the triangle is the diameter of the circle, or the triangle is acute.

What does acute mean in this context, though. It's relatively obvious that if the triangle has all angles less than 90, then a side of the triangle and the vertex opposing it are on opposite sides of the diameter of the circle (proof: consider the right angle inscribed in a circle; it's hypotenuse is always the diameter. this implies that a side and the vertex be on opposite sides in a triangle with a lesser angle).

Now consider the inscribed right triangle again. All right triangles can have one side of them as the diameter, so all right triangles have a minimum circle around them when one side is a diagonal.

Similarly, for obtuse triangles. All obtuse triangles can be included in some right triangle such that one side of the obtuse triangle is the hypotenuse of the right triangle. Therefore, the minimum circle for an obtuse triangle has a side as the diameter of the triangle.

Thus, by the triangle inequality, all non-acute triangles can be covered by a circle with diameter smaller than 1/2 the perimeter.

Now we have to use Ptolemy's theorem. (I'll try to find a link in case anyone hasn't heard of it). Apply it to the following diagram
circle diagram
The blue lines, of length y, are congruent. From Ptolemy, (a+b)y = cx. We set x constant. The length of a+b, thus the perimeter of the triangle clearly increases the greater c is. And so, all we have to consider is when c is least, which clearly happens when a is only imfinitesimally greater than the diameter of the circle. But this implies that the total perimeter greater than two times the diameter (once again by the traingle inequality). Therefore, since any other value of c would make the triangle have greater preimeter, the inequality is proven.

Brad

By Graeme Mcrae on Wednesday, February 13, 2002 - 04:19 pm:

A good reference for Ptolemy's theorem is http://www.cut-the-knot.com/proofs/ptolemy.html

A good reference for the minimum spanning circle is http://www.cs.brown.edu/people/tor/java/mec/ which gives an algorithm that makes it clear that either two or at least three points of the polygon are on the circle, and that if three points are on the circle, then the triangle formed by them contains the center of the circle in its interior.

You said c is least, "which clearly happens when a is only imfinitesimally greater than the diameter of the circle". I think you meant infinitesimally smaller than the circle.

In any case, an "infinitesimal" isn't needed, is it? Just draw a new green line, c', that is shorter than c, and draw a' and b' to meet the point of intersection of c' with the circle such that a' is a diameter of the circle. Since c' is shorter than c, it follows that

a'+b' < a+b and
a'+b'+x < a+b+x.

Since a' is a diameter, it follows that

2a' < a'+b'+x < a+b+x

which finishes the proof. Thanks for providing the bulk of this proof. I didn't see how Ptolemy helped until you added the two "y" lines for me. I appreciate that.