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[0] for r, and then see if f(r[0]) is more or less 
than Pi. If it is less, pick r[1] < r[0], but if it is more, pick 
r[1] > r[0], 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[0] would be

          N
   r[0] = (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/