## 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^{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 only be polynomially many.

keywords: Computational Geometry, Terrains

### Conference Proceedings (peer-reviewed)

János Pach, Maarten Löffler, Marc van Kreveld

How Many Potatoes are in a Mesh?

Proc. 23rd International Symposium on Algorithms and Computation

166–176, 2012

### Workshop or Poster (weakly reviewed)

János Pach, Maarten Löffler, Marc van Kreveld

How Many Potatoes are in a Mesh?

Proc. 28th European Workshop on Computational Geometry

, 2012

### Archived Publication (not reviewed)

János Pach, Maarten Löffler, Marc van Kreveld

How Many Potatoes are in a Mesh?

1209.3954, 2012

back to list