0
$\begingroup$

I have a problem where I must see if with some segments $(s1, s2 ... sn)$ I can make a polygon and if not I must cut segments to make one and count number of cuts.

I remember something from school with triangulation, but I am not tu sure if this work, I also google it and found this:

https://mathoverflow.net/questions/96617/determine-if-you-can-build-a-polygon-from-segments

Anyone can help me to go further?

$\endgroup$

1 Answer 1

0
$\begingroup$

You can always make a polygon unless the triangle inequality is not satisfied by the segments.

To clarify, let $s_k$ be the largest segment. If $s_1+s_2+...+s_{k-1}+s_{k+1}+...+s_n<s_k$ then you need to cut $s_k$ into $s_{k_1}$ and $s_{k_2}$. However, since the combined length of these two segments is greater than any of the other segments, no other cuts are required.

Therefore, you will only need 1 cut at most, possibly 0 if the triangle inequality for polygons is satisfied.

FYI: The triangle inequality for polygons involves splitting a polygon into multiple triangles and applying the original triangle inequality many times.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .