6
$\begingroup$

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

Maybe triangle inequality generalized?

$\endgroup$
  • 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 Biro May 10 '12 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$ – Misha May 10 '12 at 22:06
  • 2
    $\begingroup$ Iff (maximal side) < (sum of the rest). Is that what you want? $\endgroup$ – Anton Petrunin May 10 '12 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'Rourke May 11 '12 at 0:19
  • 1
    $\begingroup$ @spemble answer, not explore $\endgroup$ – Yemon Choi May 24 '15 at 20:51
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In your first formula shouldnt Ri be < instead of <= ? Triangule case {1,2,3} you have (1+2+3)/2 = 3 $\endgroup$ – Juan Carlos Oropeza Aug 9 '16 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$ – Taylan Aug 9 '16 at 20:08
  • 1
    $\begingroup$ In simple words it means that longest edge should be less than all other edges. $\endgroup$ – Vitaly Dyatlov Aug 9 '16 at 20:16

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