The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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?


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

   2*Pi = SUM 2*arcsin(l[i])/(2*r)),

   Pi = SUM arcsin(l[i])/(2*r)).

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+1] = -------------------*(Pi-f(r[i-1])) + r[i-1].

A reasonable value of r[0] would be

   r[0] = (SUM l[i])/(2*Pi),

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

   K = (1/4)*SUM l[i]*sqrt(4*r^2-l[i]^2).

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   
Associated Topics:
College Algorithms
College Discrete Math
College Euclidean Geometry

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.