Please help me with a reference or a proof for the following:

Find $n$ such that any convex polygon with $100$ sides can be obtained as an intersection of $n$ triangles.

First, $n \geq 34 $ since if the polygon is the intersection of $n$ triangles, each of the $100$ sides of the polygon must be contained in at least one of the triangles, therefore $3n \geq 100$. Now, I must prove that $n=34$, i.e. any polygon with 100 sides can be obtained intersecting $34$ triangles. These triangles should be formed by extending some sides of the polygon. The only problem would be that there is possible that three sides of the polygon form a triangle which does not contain the polygon, or do not form a triangle at all (if two sides are parallel).

Please help me with a reference or proof. Thank you.

  • 2
    $\begingroup$ Your first problem, that each triangle contains the polygon, should follow from whatever definition of convexity you are using. For the second, show that any side is parallel to at most one other. $\endgroup$ – deinst Aug 13 '11 at 20:17

I'm pretty sure that $n \ge 50$.

Place 100 equally spaced points along a half-circle, and draw chords between each adjacent pair of points as well as the two endpoints. You now have a 100-gon with one long side and 99 short ones.

If I'm not mistaken, there's no way for the sides of any triangle to match more than two of the short sides. Thus, this 100-gon cannot be obtained as the intersection of less than $\left\lceil \frac{99}{2} \right\rceil = 50$ triangles.

Edit: It's also easy to see that $n = 50$ is sufficient for any bounded convex 100-gon: Divide the edges into 50 pairs of adjacent sides, and for each pair extend the sides into rays starting from their common endpoint.

By convexity, these rays will not intersect the interior of the 100-gon; and by boundedness, one can pick a point on each ray such that the line joining them won't intersect the 100-gon either. These two points and the common endpoint of the rays define a triangle enclosing the 100-gon, and the intersection of the 50 triangles obtained by doing the same for each of the pairs of edges will be exactly the original 100-gon.

| cite | improve this answer | |

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.