Recognition: unknown
Convex polygons in geometric triangulations
classification
🧮 math.MG
cs.DMmath.CO
keywords
convexpolygonsboundnumberalmostauthorsbestcompute
read the original 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\"offler, 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.