Convex Polygons in Geometric Triangulations
Adrian Dumitrescu, Csaba D. Tóth · Combinatorics Probability Computing · 2017
We show that the maximum number of convex polygons in a triangulation ofnpoints in the plane isO(1.5029n). This improves an earlier bound ofO(1.6181n) established by van Kreveld, Löffler and Pach (2012), and almost matches the current best lower bound of Ω(1.5028n) due to the same authors. Given a planar straight-line graphGwithnvertices, we also show how to compute efficiently the number of convex polygons inG.