Logo

Login | Create Account

The Number of Triangulations on Planar Point Sets

Welzl, Emo (2007) The Number of Triangulations on Planar Point Sets. [Conference Paper]

Full text not available from this repository.

Abstract

We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such as the n x n integer lattice.

Item Type:Conference Paper
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:756
Deposited By:GDEA, Administration
Deposited On:04 May 2007
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springer.com/dal/home/computer/lncs?SGWID=1-164-22-173721109-0

Repository Staff Only: item control page

References

O. Aichholzer, The path of a triangulation, Proc. 15th Ann. ACM Symp. on Computational Geometry (1999), 14-23.

O. Aichholzer, T. Hackl, H. Krasser, C. Huemer, F. Hurtado, and B. Vogtenhuber, On the number of plane graphs, Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (2006), 504-513.

M. Ajtai, V. Chvatal, M. M. Newborn, and E. Szemeredi, Crossing-free subgraphs, Annals Discrete Math. 12 (1982), 9-12.

E. E. Anclin, An upper bound for the number of planar lattice triangulations, J. Combinat. Theory, Ser. A 103 (2003), 383-386.

D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Appl. Math. 65 (1996), 21-46.

M. O. Denny and C. A. Sohler, Encoding a triangulation as a permutation of its point set, Proc. 9th Canadian Conf. on Computational Geometry (1997), 39-43.

A. Garcia, M. Noy, and J. Tejel, Lower bounds on the number of crossing-free subgraphs of KN, Comput. Geom. Theory Appl. 16 (2000), 211-221.

F. Hurtado and M. Noy, Counting triangulations of almost-convex polygons, Ars Combinatorica 45 (1997), 169-179.

V. Kaibel and G. Ziegler, Counting lattice triangulations, British Combinatorial Surveys (C.D. Wensley, ed.), Cambridge University Press, 2003.

J. Matousek, P. Valtr, and E. Welzl, On two encodings of lattice triangulations, manuscript (2006).

L. McShine and P. Tetali, On the mixing time of the triangulation walk and other Catalan structures, in: DIMACS-AMS volume on Randomization Methods in Algorithm Design (Eds. P.M. Pardalos, S. Rajasekaran, and J. Rolim) DIMACS Series in Discrete Mathematics and Theoretical Computer Science 43 (1998), 147-160.

M. Molloy, B. Reed, and W. Steiger, On the mixing rate of the triangulation walk, in: DIMACS-AMS volume on Randomization Methods in Algorithm Design Eds. P.M. Pardalos, S. Rajasekaran, and J. Rolim), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 43 (1998),179-190.

S.Yu. Orevkov, Asymptotic number of triangulations in Z2, J. Combinat. Theory, Ser. A 86 (1999), 200-203.

G. Polya, On picture-writing, The American Mathematical Monthly 63 (1956), 689-697. Also in: G. L. Alexanderson, The Random Walks of George Polya, MAA, 2000.

M. Sharir, E. Welzl, Random triangulations of planar point sets, Proc. 22nd Ann. ACM Symp. on Computational Geometry (2006), 273-281.

F. Santos and R. Seidel, A better upper bound on the number of triangulations of a planar point set, J. Combinat. Theory, Ser. A 102 (2003), 186-193.

R. Seidel, On the number of triangulations of planar point sets, Combinatorica 18 (1998), 297-299.

W. S. Smith, Studies in Computational Geometry Motivated by Mesh Generation, Ph. D. Thesis, Princeton University, 1989.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.