How many potatoes are in a mesh?

DOI10.1007/978-3-642-35261-4_20zbMATH Open1260.68425arXiv1209.3954OpenAlexW2172269549MaRDI QIDQ4909533FDOQ4909533

Authors: Maarten Löffler, János Pach, Marc Van Kreveld

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: We consider the combinatorial question of how many convex polygons can be made by using the edges taken from a fixed triangulation of n vertices. For general triangulations, there can be exponentially many: we show a construction that has Omega(1.5028^n) convex polygons, and prove an O(1.62^n) upper bound in the worst case. If the triangulation is fat (every triangle has its angles lower-bounded by a constant delta>0), then there can be only polynomially many. We also consider the problem of counting convex outerplanar polygons (i.e., they contain no vertices of the triangulation in their interiors) in the same triangulations. In this setting, we get the same exponential bounds in general triangulations, and lower polynomial bounds in fat triangulations. If the triangulation is furthermore compact (the ratio between the longest and shortest distance between any two vertices is bounded), the bounds drop further to Theta (n^2) for general convex outerplanar polygons, and Theta (n) for fat convex outerplanar polygons.

Full work available at URL: https://arxiv.org/abs/1209.3954

Recommendations

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Cited In (7)

This page was built for publication: How many potatoes are in a mesh?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909533)