And this is what guarantees a triangulation for every simple polygon. For further challenge see problem #6 in the second session of iranian tst-s

ikap wrote: And this is what guarantees a triangulation for every simple polygon. For further challenge see problem #6 in the second session of iranian tst-s I think your solution is true when we know that we can triangulation a polygon but how we can prove this when we do not konw we can triangulation a polygon????(sorry for my bad english)>

Here's a sketch of how to prove both the result in the original problem and that any polygon has a triangulation. There are three places in the argument I'm marking with (**) that you should try and convince yourself of in more detail. Lemma: For any (simple) polygon there is a diagonal lying within the polygon (perhaps not cutting off a triangle) Proof: Place the polygon arbitrarily in the plane, and let $ z_1$ be a vertex having maximal $ y$ coordinate. Note that the angle at $ z_1$ must be less than $ 180$ degrees. Let $ z_0$ and $ z_2$ be the adjacent vertices to $ z_1$. Either the triangle $ z_0 z_1 z_2$ lies inside the polygon (in which case we are done already), or there must be other vertices of the polygon inside this triangle (**). Let $ z$ be the vertex inside the triangle which is furthest from the line segment $ z_0 z_2$. Then $ z z_1$ is our required diagonal, for if an edge crossed it one of its endpoints would be further from the segment (**). Using this, we can inductively triangulate the polygon by first drawing a diagonal inside, then triangulating each of the two smaller polygons formed by this diagonal. Since in any triangulation at least one triangle uses two adjacent sides from the polygon (**), this also proves the original problem.