Maximum Area Given Enclosing Lengths
Date: 11/21/2001 at 02:16:53 From: Arun Kishore Subject: Maximum Area Given Enclosing Lengths Hello Doctor, I am given a set of N line segments with lengths l[i], 1 <= i <= N and I am supposed to calculate the maximum area that can be enclosed using all of these line segments. Is there an efficient method of finding the solution? For instance, for values of N <= 100? Regards, Ustaad
Date: 11/21/2001 at 16:20:05 From: Doctor Rob Subject: Re: Maximum Area Given Enclosing Lengths Thanks for writing to Ask Dr. Math. This is a very interesting problem. I have an approach that will give you a numerical answer, but I don't know how to solve it to get a symbolic answer. The largest area is obtained when the N-gon has all its vertices on a circle. The hard part is to find the radius r of that circle. If you connect the ends of each line segment to the center of the circle, you will have an isosceles triangle with sides r, r, and l[i]. The vertex angle of this triangle is 2*arcsin(l[i]/(2*r)). The sum of all the vertex angles is 2*Pi radians. This means that N 2*Pi = SUM 2*arcsin(l[i])/(2*r)), i=1 N Pi = SUM arcsin(l[i])/(2*r)). i=1 This last equation determines the value of r, but I can't solve it algebraically. Call the right-hand side of this equation f(r). I would start with a guess r for r, and then see if f(r) is more or less than Pi. If it is less, pick r < r, but if it is more, pick r > r, and try again. Repeat this until you have r caught between r[i] and r[i-1]. Then the next guess should be determined by using linear interpolation: (r[i]-r[i-1]) r[i+1] = -------------------*(Pi-f(r[i-1])) + r[i-1]. (f(r[i])-f(r[i-1])) A reasonable value of r would be N r = (SUM l[i])/(2*Pi), i=1 which must be too small, but not too far off. Using this technique, the sequence r[i] will converge pretty rapidly to r. In this way, you can determine the numerical value of r to as much accuracy as needed. Then the total area is given by the formula N K = (1/4)*SUM l[i]*sqrt(4*r^2-l[i]^2). i=1 This procedure should be quite efficient, the hard part being the computation of N arcsines at each iteration. Feel free to write again if I can help further. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.