A peer of mine gave me the following problem :
Given a sequence of $n$ lengths (i.e.,$L_1, L_2, .., L_n$ ) where each is the length of the side, find a sequence of $n$ points (where $p_k = (x_k, y_k)$) such that $dist(p_k, p_{k+1}) = L_k$ and $dist(p_1, p_n) = L_n$ where $dist(a, b)$ is the Euclidean distance between points $a$ and $b$.
Note that the first point , $p1$, must be $(0, 0)$ and the second point , $p_2$, must be $(0, L_1)$ .
These points must correspond to the ordered clockwise vertices of the simple polygon having the maximum possible area for the given side lengths.
Determine the coordinates of the points that correspond to a polygon of maximal area.
Now, I've seen some similar problems, but this one I don't even know how to begin with. Determining the maximum area is quite easily done by Brahmagupta's formula, but the actual finding of the points seems really hard.
The only thing I could think of was finding some sort of enclosing circle and then trying to determine the points, but that's not even a starting point.
Any ideas on how to solve this?
Best Answer
(As far as I can see, the online competition is now over, so I shall reinstate my answer as promised.)
As commented by hardmath, and agreed by the OP, the solution is a cyclic polygon whose vertices lie on a common circle.
Note that if one of the line segments would be longer than the sum of the length of the rest of the line segments, they cannot form a polygon. Because of this, we know that $$L_i \le \sum_{k \ne i}^{n} L_k$$ for all $i = 1 \ldots n$. (This also means that $0 \le \theta_i \lt \pi$.)
Each of the $n$ line segments essentially forms an isosceles triangle with the center of the common circle. Two of the sides are of length $r$, the radius of the common circle, and the third is the line segment itself, length $L_i$. (Essentially, we can decompose the polygon into triangular wedges, each being an isosceles triangle. This also means that the order of the line segments does not affect the area, as reordering the triangular parts does not change their areas.)
The length of a circular chord fulfills $$L_i = 2 r \sin\left(\frac{\theta_i}{2}\right)$$ Here, $\theta_i$ is the angle between the $r$-length edges in the isosceles triangles. Solving for $\theta_i$, we see that $$\theta_i = 2 \arcsin \left( \frac{L_i}{2 r} \right) = \arccos \left( 1 - \frac{ L_i^2 }{2 r^2} \right)$$ because $2 \arcsin(x) = \arccos(1 - 2 x^2)$ when $0 \le x \le 1$.
Note that this also means that $$\frac{d \, \theta_i}{d \, r} = - \frac{2 L}{\sqrt{4 r^4 - L^2 r^2}}$$
In order for the figure to be a polygon, the sum of the angles $\theta_i$ must equal $180°$: $$\sum_{i=1}^{n} \theta_i = 2 \pi$$
Combining the above two, and dividing by two, we get $$\sum_{i=1}^{n} \arcsin \left( \frac{L_i}{2 r} \right) = \pi$$ which we can use to numerically solve for $r$.
In order for each $\theta_i$ to exist, $\max(L)/(2r) \le 1$. This means that $r \ge \max(L)/2$, and that $r_{min} = \max(L)/2$ is the minimum allowed radius in the numerical methods.
We also know that the radius must be less than half the perimeter, so $r_{max} = (\sum_i L_i) / 2$.
When we have found the $r$ for which $\sum_i \theta_i = 2 \pi$, we can compute the vertex coordinates. Since the points are to be in clockwise order, we can use $$\begin{cases} x_i' = x_0 - r \cos \varphi_i \\ y_i' = y_0 + r \sin \varphi_i \\ \end{cases}$$ where $$\begin{cases} x_0 = r \cos \varphi_1 \\ y_0 = -r \sin \varphi_1 \end{cases}$$ and $$\varphi_i = \begin{cases} -\frac{\theta_i}{2}, & i = 1 \\ -\frac{\theta_i}{2} + \sum_{k=1}^{i-1} \theta_i, & 2 \le i \le n \end{cases}$$ The above gives us $\varphi_1 = -\theta_1/2$ and $\varphi_2 = -\varphi_1 = \theta_1/2$, so the first line segment will be vertical; $x_1 = x_2 = y_1 = 0$, $y_2 \gt 0$ (in fact $y_2 = L_1$).
The above therefore yields $x_1 = 0$, $y_1 = 0$, $x_2 = 0$, $y_2 = L_1$, with the rest of the vertices $(x_i, y_i)$ in clockwise order around the center at $(x_0, y_0)$.
Here is an example program that reads line lengths from standard input, and uses a binary search to find the radius with at least six digits of precision, outputting the vertex coordinates to standard output. example.c:
Compile it using e.g. in Linux
and run it, generating say 10 random line lengths as input, using
Here is an example of the output, first 12 lines to standard error, followed by 10 lines to standard output: