On numbers of pseudo-triangulations
作者： Moria Ben-Ner , André Schulz , Adam Sheffer
DOI: 10.1016/J.COMGEO.2012.11.002
关键词:
摘要: We study the maximum numbers of pseudo-triangulations and pointed that can be embedded over a specific set points in plane or contained triangulation. derive bounds O(5.45^N) @W(2.41^N) for number triangulation N points. For all we O^@?(6.54^N) @W(3.30^N). also prove O^@?(89.1^N) any plane, at most 120^N general pseudo-triangulations.
arxiv.org
harvard.edu
sci-hub.se 参考文章(22)
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
Hannes Krasser, Oswin Aichholzer, The point set order type data base: A collection of applications and results. canadian conference on computational geometry. pp. 17- 20 ,(2001)
Adam Sheffer, Micha Sharir, Counting Plane Graphs: Cross-Graph Charging Schemes arXiv: Computational Geometry. ,(2012)
Francisco Santos, Ileana Streinu, Guenter Rote, Pseudo-Triangulations - a Survey arXiv: Combinatorics. ,(2006)
Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba D. Tóth, Emo Welzl, Counting plane graphs: flippability and its applications workshop on algorithms and data structures. pp. 524- 535 ,(2011) , 10.1007/978-3-642-22300-6_44
Günter Rote, Jack Snoeyink, Dana Randall, Francisco Santos, Counting triangulations and pseudo-triangulations of wheels. canadian conference on computational geometry. pp. 149- 152 ,(2001)
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
Micha Sharir, Adam Sheffer, Emo Welzl, On degrees in random triangulations of point sets Journal of Combinatorial Theory, Series A. ,vol. 118, pp. 1979- 1999 ,(2011) , 10.1016/J.JCTA.2011.04.002
Ileana Streinu, Acute Triangulations of Polygons Discrete and Computational Geometry. ,vol. 34, pp. 587- 635 ,(2005) , 10.1007/S00454-005-1184-0
P. Hall, On Representatives of Subsets Journal of The London Mathematical Society-second Series. pp. 26- 30 ,(1935) , 10.1112/JLMS/S1-10.37.26