In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) $P$ into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$.

Question : Prove that every triangulation of a finite point set $S$ contains $3|S|-3-h$ edges, where the boundary of $ConvexHull(S)$ contains $h$ edges.

Note : I think the method of proof is induction. But, I don't know which variable i should use for the induction.

  • $\begingroup$ Have you heard about the Euler characteristic? That being said, letting $|S|$ be the induction variable is probably not a bad idea. $\endgroup$ – Arthur Nov 11 '16 at 11:32
  • $\begingroup$ @Arthur Yeah i know it ... ok, i'm gonna try ... if i failed, i'd edit my question and write more details about my try ... $\endgroup$ – Arman Malekzadeh Nov 11 '16 at 11:56

Your Answer

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

Browse other questions tagged or ask your own question.