Convex polygons in geometric triangulations

Abstract

We show that the maximum number of convex polygons in a triangulation of $n$ points in the plane is $O(1.5029^n)$. This improves an earlier bound of $O(1.6181^n)$ established by van Kreveld, Löffler, and Pach (2012) and almost matches the current best lower bound of $\Omega (1.5028^n)$ due to the same authors. Given a planar straight-line graph $G$ with $n$ vertices, we show how to compute efficiently the number of convex polygons in $G$.

20 pages, 6 figures, a preliminary version has been presented at WADS 2015

References in corpus (4)

• Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
• Counting Carambolas
• Convex polygons in geometric triangulations
• Counting Triangulations and other Crossing-free Structures via Onion Layers

Cited by in corpus (1)

• Convex polygons in geometric triangulations