pith. machine review for the scientific record. sign in

arxiv: 1411.1303 · v3 · submitted 2014-11-04 · 🧮 math.MG · cs.DM· math.CO

Recognition: unknown

Convex polygons in geometric triangulations

Authors on Pith no claims yet
classification 🧮 math.MG cs.DMmath.CO
keywords convexpolygonsboundnumberalmostauthorsbestcompute
0
0 comments X
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.