How Many Potatoes are in a Mesh?

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

How Many Potatoes are in a Mesh?

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

Abstract

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.

Original language	English
Title of host publication	Proc. 28th European Workshop on Computational Geometry
Publication status	Published - 2012

Keywords

CG, TIN

Cite this

@inproceedings{d9c772ddf0204e0280570cc19a4d81d4,

title = "How Many Potatoes are in a Mesh?",

abstract = "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 = "CG, TIN",

author = "Kreveld, {Marc van} and Maarten L{\"o}ffler and J{\'a}nos Pach",

year = "2012",