0
$\begingroup$

I'm studying for a computational geometry exam and I found this question on one of the past years' exams - "give a 5-sided polygon in R^2 with exactly 2 triangulations". I've found lots of information on the number of triangles in a polygon's triangulation and the number of sides in a triangulation, but nothing about the number of triangulations a polygon can have (except for convex polygons, which this clearly can't be since a 5-sided convex polygon has 5 triangulations - the 3rd Catalan number, right?). How do I solve something like this?

$\endgroup$
0
$\begingroup$

A triangulation of a 5gon is determined by one special vertex, at which two diagonals end. So our 5gon shall have to such vertices. Can these vertices be neighbours, say $A$ and $B$? No, because with diagonal $AC$, $AD$, and $BD$, $BE$, we also have the two diagonals ending at $D$ and hence a third triangulation. Hence the two special vertices are not adjacent, so wlog they are $A$ and $C$, and we have diagonals $AC$, $AD$, and $CE$. Thus $B$ must be blocked from "seeing" $D$ or $E$.

enter image description here

$\endgroup$
2
  • $\begingroup$ Thank you, that makes sense :) $\endgroup$ Jan 20 '18 at 21:26
  • $\begingroup$ Are there similar approaches for (any/all) other dimensions? $\endgroup$ Jan 20 '18 at 22:14

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.