How Many Potatoes Are in a Mesh?

摘要

We consider the combinatorial question of how many convex polygons can be made at most by using the edges taken from a fixed triangulation of n vertices. For general triangulations, there can be exponentially many: Ω( 1.5028~n) and O(1.62~n) in the worst case. If the triangulation is fat (every triangle has its angles lower-bounded by a constant δ> 0), then there can be only polynomially many: Ω(n~(1/2[2π/δ]) ) and O(n~([π/δ])). If we count convex polygons with the additional property that they contain no vertices of the triangulation in their interiors, we get the same exponential bounds in general triangulations, and Ω(n~([2π/3δ])) and O(n~([2π/3δ])) in fat triangulations.