Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a way to determine whether it is possible to build a polygon from given n segments?

Maybe triangle inequality generalized?

share|improve this question
1  
Are you asking if $n$ given segments are polygonalizable, or if there exists a polygon with a given set of $n$ side lengths? –  Michael Biro May 10 '12 at 22:04
3  
What is your definition of a polygon? Does it have to be embedded? If not then the answer is essentially given by triangle inequalities: Every edge is at most half of the perimeter $\iff$ there exists a polygon with the given side-lengths. –  Misha May 10 '12 at 22:06
    
@Misha: Why the caveat about embeddability? –  Vectornaut May 10 '12 at 22:22
2  
Iff (maximal side) < (sum of the rest). Is that what you want? –  Anton Petrunin May 10 '12 at 22:37
2  
I would like to add to Misha's and Anton's equivalent answers that, not only does a polygon exist, but a convex polygon exists, and in fact, by alignment of segments, a triangle exists. –  Joseph O'Rourke May 11 '12 at 0:19
show 3 more comments

closed as too localized by Anton Petrunin, Gerry Myerson, Yemon Choi, Anthony Quas, Gjergji Zaimi May 11 '12 at 14:20

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

The answer is: Given a collection of positive numbers $r_1,...,r_n$, there exists a polygon in $R^2$ with the side-lengths $r_1,...,r_n$ if and only if for every $i$, $$ r_i\le \frac{1}{2}(r_1+...+r_n) $$ which is just a form of triangle inequalities (equivalently, every side is at most the sum of the rest of the sides). If you do not accept degenerate polygons as legitimate polygons then in the above answer you replace non-strict inequalities with the strict ones.

There are different ways to prove this, one is to use elementary Euclidean geometry, I will explain a better solution, which uses hyperbolic geometry, since it teaches you something interesting. Suppose that $r_1,...,r_n$ satisfy the strict triangle inequalities above. Now, think of the numbers $r_i$ was masses and place them at distinct points $x_i$ on the unit circle $S^1$. The result is a finite measure $\mu$ on $S^1$. The triangle inequalities ensure that this measure is stable, therefore, the measure $\mu$ has (unique) conformal barycenter $c(\mu)$ in the open unit disk $D^2$, which you regard as a model of the hyperbolic plane. Since conformal barycenter is preserved by hyperbolic isometries, there exits a hyperbolic isometry $g$ of $D^2$, so that $g_*(\mu)$ has conformal center at the center $0$ of the disk. Let $v_i:=g(x_i)$, $i=1,...,n$. By the properties of the conformal barycenter, $c(\mu)=0$ if and only if the Euclidean barycenter of the measure $\mu$ is also at zero. Thus, $$ \sum_{i=1}^n r_i v_i=0. $$ This means that you get a closed polygon $P$ in the Euclidean plane whose edges are represented by the vectors $r_i v_i, i=1,...,n$. The polygon $P$ you get need not be embedded. However, you can triangulate $P$ from a single vertex and then inductively straighten it to get an embedded polygon if you wish. Alternatively, if you choose points $x_i$ on the circle in their natural cyclic order $1,...,n$, then the resulting polygon $P$ will be convex.

See here for the details and here for generalizations.

This argument above has interesting generalizations, with hyperbolic plane replaced by the symmetric space of the group $GL(n)$ (and other symmetric spaces and buildings), which allow one to solve the problem about eigenvalues of sums of symmetric matrices and other problems in algebra.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.