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?

Regards,
```

```
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

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search