Convex polygons in geometric triangulations
作者： Adrian Dumitrescu , Csaba D. Tóth
DOI: 10.1017/S0963548317000141
关键词:
摘要: We show that the maximum number of convex polygons in a triangulation $n$ points plane is $O(1.5029^n)$. This improves an earlier bound $O(1.6181^n)$ established by van Kreveld, L\"offler, and Pach (2012) almost matches current best lower $\Omega(1.5028^n)$ due to same authors. Given planar straight-line graph $G$ with vertices, we how compute efficiently $G$.
harvard.edu
arxiv.org
sci-hub.st 参考文章(25)
M. Ajtai, V. Chvátal, M.M. Newborn, E. Szemerédi, Crossing-Free Subgraphs Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday. ,vol. 60, pp. 9- 12 ,(1982) , 10.1016/S0304-0208(08)73484-4
Andreas Razen, Emo Welzl, Counting plane graphs with exponential speed-up Rainbow of computer science. pp. 36- 46 ,(2011) , 10.1007/978-3-642-19391-0_3
P. Erdös, G. Szckeres, A combinatorial problem in geometry Compositio Mathematica. ,vol. 2, pp. 463- 470 ,(2009) , 10.1007/978-0-8176-4842-8_3
Andreas Razen, Jack Snoeyink, Emo Welzl, Number of Crossing-Free Geometric Graphs vs. Triangulations Electronic Notes in Discrete Mathematics. ,vol. 31, pp. 195- 200 ,(2008) , 10.1016/J.ENDM.2008.06.039
Manuel Wettstein, Counting and Enumerating Crossing-free Geometric Graphs symposium on computational geometry. pp. 1- 10 ,(2014) , 10.1145/2582112.2582145
Birgit Vogtenhuber, Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, On the Number of Plane Geometric Graphs Graphs and Combinatorics. ,vol. 23, pp. 67- 84 ,(2007) , 10.1007/S00373-007-0704-5
Victor Alvarez, Raimund Seidel, A simple aggregative algorithm for counting triangulations of planar point sets and related problems symposium on computational geometry. pp. 1- 8 ,(2013) , 10.1145/2462356.2462392
JacobE. Goodman, On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato Geometriae Dedicata. ,vol. 11, pp. 99- 106 ,(1981) , 10.1007/BF00183192
Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel, Counting triangulations and other crossing-free structures approximately Computational Geometry: Theory and Applications. ,vol. 48, pp. 386- 397 ,(2015) , 10.1016/J.COMGEO.2014.12.006
J. S. Chang, C. K. Yap, A polynomial solution for the potato-peeling problem Discrete & Computational Geometry. ,vol. 1, pp. 155- 182 ,(1986) , 10.1007/BF02187692