How Many Potatoes are in a Mesh?

We consider the combinatorial question of how many convex polygons can be made by using the edges taken from a fixed triangulation. For general triangulations there can be exponentially many: Ω(1.5028ⁿ) and O(1.62ⁿ) in the worst case. If the triangulation is fat (every triangle has its angles lower-bounded by a constant δ > 0), then there can only be polynomially many.

slides

Conference Proceedings (peer-reviewed)

Workshop or Poster (weakly reviewed)

Archived Publication (not reviewed)

back to list