Convex Polygons in Geometric Triangulations

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 Ω(1.5028 n ) due to the same authors. Given a planar straight-line graph G with n vertices, we also show how to compute efficiently the number of convex polygons in G .