wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> A characterization of regular n-gons
        
(Message started by: ecoist on Nov 15^th, 2007, 8:48pm)

Title: A characterization of regular n-gons
Post by ecoist on Nov 15^th, 2007, 8:48pm

This is suggested by ThudanBlunder's Largest Ellipse Inside a Pythagorean Triangle?.

Show that an n-gon circumscribing a circle such that every side is tangent to the circle and having minimum area among all such must be a regular n-gon.

Title: Re: A characterization of regular n-gons
Post by Aryabhatta on Nov 19^th, 2007, 4:10pm

Interesting problem... *bump*

Title: Re: A characterization of regular n-gons
Post by Obob on Nov 19^th, 2007, 6:16pm

This ended up being a heck of a lot longer than I thought it would be.

[hide]
Consider the following question: let 0 < t < pi, and construct the tangent lines to the unit circle x² + y² = 1 at (1,0) and (cos t, sin t). Denote by A the area of the region bounded by the two tangent lines and the unit circle. What is A?

Let's give our points some names. Let P be the point (cos t, sin t), and Q the point (1, 0). Let O=(0,0) be the origin, and the center of the circle C. Let R be the point where the tangent lines to P and Q meet, and let S be the point where segment OR meets C.

Line OR bisects angle POQ, and the triangles OPR and OQR are congruent. One half the area A is thus equal to the area of the triangle OQR minus the circular sector QOS. Sector QOS has angle t/2, so its area is (t/2)/(2 pi) * pi = t/4.

To find the area of OQR, we need to know the y-coordinate of R. For this, we find the equation of the tangent line to P. Its slope is -cot t, so its equation is y-sin t=-cot t(x - cos t). At x=1, we thus have y=sin t - cot t + cot t cos t = csc t - cot t. Then triangle OQR is a right triangle with base of length 1 and height of length csc t - cot t. So its area is (csc t - cot t)/2.

We finally conclude that A = csc t - cot t - t/2.

Now for the application to the original problem. Suppose we have three points in order on a circle. By forming tangent lines at these three points, we get two regions of the type we considered above: one by considering the first two, and one by considering the last two. The claim is that the sum of the areas of these two regions will be at a minimum exactly when the second point makes the same angle with the first point as it does the third. That is, if we hold the first and third points fixed and move the second between the first and third then the sum of the two areas should be minimized when the second point is exactly between the first and third.

In light of our earlier derivation, this means that the function f(s) = csc (t-s) - cot (t-s) - (t-s)/2 + csc s - cot s - s/2 of s should be minimized at s=t/2; here we let s vary from min{0,t - pi} to min{t,pi}, and t is fixed between 0 and 2 pi. Differentiating with respect to s, we get

f'(s) = -cot s csc s + csc² s + cot(s-t)csc(s-t) - csc² s-t,

and differentiating with respect to s again gives

f''(s) = 1/2 * (sec²(s/2) tan(s/2) - sec²((s-t)/2) tan((s-t)/2)).

Now 0 < s/2 < pi / 2, so tan(s/2)>0, and -pi/2 < (s-t)/2 < 0, so tan((s-t)/2)<0. Since sec x => 1 for -pi/2 < x < pi/2, we conclude that f''(s)>0 for all s. Thus f'(s) is increasing, and has at most one zero. It visibly has a zero at s=t/2, so s=t/2 is a critical point of f. Moreover, since f' is increasing, s=t/2 is where f attains its minimum.

Now given any collection of points around the circle, a unique circumscribing polygon exists whose edges consist of segments of the tangent lines at those points. If the angles between two adjacent pairs of points are not equal, we can decrease the area of the polygon by replacing the middle point with the point exactly in between the other two points, as seen in the above analysis. Thus in order for the area of the polygon to be minimal, it is necessary that all the points are spaced equally along the circle. Clearly then the polygon is regular.

We can also use a similar argument to show that the regular polygons are area minimizing among circumscribing n-gons. Consider the space X of (possibly not strictly) increasing n-tuples of angles differing consecutively by no more than pi, that is, sequences of the form (t₁,t₂,...,t_n), where t_i+1 - pi <= t_i <= t_i+1. This is a closed and bounded subset of Rⁿ, so it is compact.

Let U be the subset of X consisting of tuples which actually define polygons. This is the subset consisting of tuples where no two consecutive angles are equal or differ by exactly pi, and where the first and last tuple are not 0 and 2 pi, respectively. On U we can define a function "Area" to be the function assigning to a tuple the area of the corresponding polygon. Area is a continuous function U->R. We can also define n functions "Consecutive angle difference" on X, by letting the ith consecutive angle difference function give the difference t_i+1-t_i, with the obvious modification in the case i=n. These are all continuous functions on X. Notice that U is described as the locus of X where none of the consecutive angle difference functions are either 0 or pi.

Now suppose we have any circumscribing n-gon, call it P₀. We can construct a new polygon P₁ by finding a triple of points where the consecutive angle differences are not the same and replacing the middle point with the point in between the first and the third. The effect of this on the two corresponding consecutive angle difference functions is to replace their values with their average. The area function decreases when we pass from P₀ to P₁.

If we repeat this procedure over and over again, it is possible to make the consecutive differences tend to 2 pi/n in the limit. This is because the sum of the n consecutive differences is 2 pi, and we are averaging them with one another over and over again. The rigorous argument behind this is a little messy, but at least it is intuitively clear.

Hence we have constructed a sequence of elements of X (in fact U). Since X is compact, it has a convergent subsequence. The limit has consecutive differences all equal to 2 pi/n, so is a regular polygon. And the area of the limit is no larger than the area of the original polygon, since the area has decreased each step of the way and area is continuous on U. Therefore the regular polygon minimizes area.
[/hide]

Title: Re: A characterization of regular n-gons
Post by ecoist on Nov 19^th, 2007, 8:45pm

A proof of this problem follows quickly from a property of convex functions which I am, so far, unable to prove (or disprove). A real function f(x) is convex in the interval [x,y] if

f(rx+(1-r)y)<rf(x)+(1-r)f(y), for all r such that 0<r<1.

The relevant property is the generalization:

Let f(x) be convex in the interval [a,b]. Let x_i, i=1 to n, be in [a,b]. Let a_i, for i=1 to n satisfy a_i>0, for all i, and a₁+...+a_n=1. Then

f(a₁x₁+...+a_nx_n)<a₁f(x₁)+...+a_nf(x_n).

Can someone prove this?

Title: Re: A characterization of regular n-gons
Post by Obob on Nov 20^th, 2007, 1:48pm

That is just Jensen's inequality. Care to elaborate a bit on how it is relevant, though?

Title: Re: A characterization of regular n-gons
Post by ecoist on Nov 20^th, 2007, 2:30pm

Thanks much, Obob! I found a simple inductive proof of Jensen's inequality on Wikipedia. As for elaborating on its relevance, I'm afraid that I might give away the clever solution sent to me.

Title: Re: A characterization of regular n-gons
Post by ecoist on Nov 21^st, 2007, 4:49pm

My comment to Obob seems a bit silly given we have one solution to this problem, so here is the solution using Jensen's inequality.

[hide]We may assume that the inscribed circle has radius 1. By drawing lines from the center of the circle to the n vertices of the n-gon and to its n points of tangency with the circle, the n-gon is dissected into 2n right triangles, each with one arm a radius of the circle and the other arm a portion of the perimeter of the n-gon. Since the radius of the circle is 1, the area of each right triangle is half the the length of the other arm, or, half the tangent of the angle opposite this arm. Hence the area of the n-gon is half the perimeter p of the n-gon, or half the sum of 2n tangents of angles, each less than 90 degrees. The sum of these angles is, of course, 360 degrees. The tangent function is convex in the interval [0,90]; so, by Jensen's inequality,

p/2n=(sum of 2n tangents)/2n>tan(360/2n), or p>2n tan(360/2n).

Hence the area of the n-gon satisfies p/2>n tan(360/2n). Since n tan(360/2n) is the area of a regular n-gon circumscribing a circle of radius 1, it follows that a regular n-gon has the least area among n-gons circumscribing a circle of radius 1.[/hide]

Title: Re: A characterization of regular n-gons
Post by Obob on Nov 23^rd, 2007, 1:47pm

Very nice, ecoist. And much more elementary than my solution, as well. It's nice that it proves the regular polygon minimizes area in the same argument that it proves minimizing polygons are regular.

Title: Re: A characterization of regular n-gons
Post by ecoist on Nov 23^rd, 2007, 2:50pm

Thanks, Obob, but I merely paraphrased professor Bogomolny of cut-the-knot.org.

Title: Re: A characterization of regular n-gons
Post by Obob on Nov 23^rd, 2007, 4:14pm

Actually, I may have spoken too soon. The argument does nicely show that the regular n-gon is area minimizing. But does it actually show that it is the unique area minimizer? That is, why does equality in our application of Jensen's inequality require that the n points of tangency on the circle are spaced equally? This is not clear to me, and is what the first (and more difficult) half of my argument showed.

The second half of my argument was more or less just a compactness argument to prove that a minimizer exists (and thus must be the regular polygon). As hand-wavey as it was, the Jensen's inequality argument definitely improves on it drastically.

Title: Re: A characterization of regular n-gons
Post by Obob on Nov 23^rd, 2007, 4:27pm

In retrospect, I think it is actually pretty easy to see that equality holds exactly when all the angles are the same. This should follow from the fact that tan is strictly convex on [0,pi/2].