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$
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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