Is there a way to determine whether it is possible to build a polygon from given n segments?
Maybe triangle inequality generalized?
10
-
1$\begingroup$ Are you asking if $n$ given segments are polygonalizable, or if there exists a polygon with a given set of $n$ side lengths? $\endgroup$– Michael BiroMay 10, 2012 at 22:04
-
3$\begingroup$ 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. $\endgroup$– MishaMay 10, 2012 at 22:06
-
2$\begingroup$ Iff (maximal side) < (sum of the rest). Is that what you want? $\endgroup$– Anton PetruninMay 10, 2012 at 22:37
-
2$\begingroup$ 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. $\endgroup$– Joseph O'RourkeMay 11, 2012 at 0:19
-
1$\begingroup$ @spemble answer, not explore $\endgroup$– Yemon ChoiMay 24, 2015 at 20:51
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ In your first formula shouldnt
Ribe<instead of<=? Triangule case{1,2,3}you have(1+2+3)/2 = 3$\endgroup$ Aug 9, 2016 at 15:48 -
2$\begingroup$ @JuanCarlosOropeza It states "If you do not accept degenerate polygons as legitimate polygons then in the above answer you replace non-strict inequalities with the strict ones.". You can create a degenerate polygon with
{1, 2, 3}, which will look like a single line. $\endgroup$– TaylanAug 9, 2016 at 20:08 -
1$\begingroup$ In simple words it means that longest edge should be less than all other edges. $\endgroup$ Aug 9, 2016 at 20:16