Article contents
Convex Polygons in Geometric Triangulations†
Published online by Cambridge University Press: 30 May 2017
Abstract
We show that the maximum number of convex polygons in a triangulation of n points in the plane is O(1.5029n). This improves an earlier bound of O(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 graph G with n vertices, we also show how to compute efficiently the number of convex polygons in G.
MSC classification
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2017
Footnotes
An extended abstract of this paper appeared in the Proceedings of the 29th International Symposium on Algorithms and Data Structures (WADS 2015), Vol. 9214 of Lecture Notes in Computer Science, Springer, 2015, pp. 289–300.
References
- 3
- Cited by