Maximizing Irregular Polygon Area: Which Circle?Date: 05/01/2011 at 12:00:03 From: Phil Subject: Max. area irregular n-gon, given sides only (no angles). It is well known that an irregular n-gon, given side lengths only, will enclose maximum area iff all n vertices lie on a circle. The problem is, how does one find the radius of that circle? Given the circle, draw radii from the center to each vertex of the n-gon, dividing the figure into n sectors. The sine of the central half angle of each sector is equal to 1/2 S/R, where S is the given length of the side of the n-gon, and R is the (unknown) radius of the circle. The half central angles must add to 180 degrees. However, I see no easy way to get from the sum of the sines to the sum of the angles expressed as a function of R, which would permit solving for R. P.S. I'm 86 years old, so don't wait too long to solve this! Date: 05/03/2011 at 21:34:23 From: Doctor Vogler Subject: Re: Max. area irregular n-gon, given sides only (no angles). Hi Phil, Thanks for writing to Dr. Math. So, you have a finite list of sides: S_1, S_2, S_3, ... S_n And you know that the polygon with those sides (in that order) has its vertices on a circle of radius R, to use your label. The half-angle (measured at the circle's center) of the sector corresponding to side S_i is some angle t_i between 0 and 180 degrees (or pi radians). You know that the angles t_i sum to 180 degrees exactly, and that sin(t_i) = (S_i)/(2R). You want to solve for R. My first thought is to solve for the t_i's using your equation, giving t_i = arcsin(S_i/2R), and to then solve this equation for R: n sum arcsin(S_i/2R) = pi i=1 That doesn't look like something you could express in a closed form, although you could solve it using numerical techniques such as Newton's Method. Alternately -- for a conceptually simpler approach -- note that since S_i/2R decreases as R increases, and arcsin is an increasing function, the summation will be decreasing as R increases. You could use that fact to find R with, for example, a binary search, although this will probably converge more slowly than Newton's Method. For example, I did the following with the free math program GNU Pari, which you can download from http://www.math.u-bordeaux1.fr/~belabas/pari/ In Pari, I define a list of sides like so: s=[3,4,5,6] Next I have Pari determine the largest side length (R must be at least half this) and the sum of all of the sides (R must be smaller than that). Then I use Pari's built-in "solve" function to do a binary search and find the answer: maxs=vecsort(s)[length(s)] sums=sum(i=1,length(s),s[i]) f(r)=sum(i=1,length(s),asin(s[i]/(2*r))) solve(r=maxs/2,sums,f(r)-Pi) But I noticed one problem: if any of the half-angles t_i is larger than 90 degrees, then this does not give the correct value: arcsin(S_i/2R) Rather, this does: pi - arcsin(S_i/2R) (Try s = [3, 4, 6], for example.) When that happens, the above computation will already give f(maxs/2) < Pi Now you know that the largest side S_i is the one with the big sector, and its half-angle should be pi - arcsin(S_i/2R) So we could modify the program to check both cases: maxs=vecsort(s)[length(s)] sums=sum(i=1,length(s),s[i]) f(r)=sum(i=1,length(s),asin(s[i]/(2*r))) if( f(maxs/2)<Pi, g(r)=f(r)-2*asin(maxs/(2*r)), g(r)=f(r)-Pi ) solve(r=maxs/2,sums,g(r)) I thought about trying to use arccos instead of arcsin, since arccos has a range of [0, pi] instead of [-pi/2, pi/2], but then the rest of the formula gets messy, since it involves square roots and so forth. Of course, the above will fail if the largest side is greater than or equal to the sum of the other sides, for obvious reasons. It is interesting to notice that reordering the side lengths changes the polygon but does not change the radius R. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 05/07/2011 at 16:21:50 From: Phil Subject: Thank you (Max. area irregular n-gon, given sides only (no angles).) Dear Dr. Vogler: Thank you for your interest. You have more or less confirmed my suspicion that a neat, closed form solution likely does not exist. Thanks for your reference to the Pari program. I am definitely going to try it. V.T.Y., Phil Epstein |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/