Random triangulations of planar point sets
Authors:
Open Access
- 5 June 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 273-281
Abstract
Let S be a finite set of n+3 points in general position in the plane, with 3 extreme points and n interior points. We consider triangulations drawn uniformly at random from the set of all triangulations of S, and investigate the expected number, vi, of interior points of degree i in such a triangulation. We provide bounds that are linear in n on these numbers. In particular, n/43≤v3≤ (2n+3)/5.Moreover, we relate these results to the question about the maximum and minimum possible number of triangulations in such a set S, and show that the number of triangulations of any set of n points in the plane is at most 43n, thereby improving on a previous bound by Santos and Seidel.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Random planar graphsJournal of Combinatorial Theory, Series B, 2005
- A better upper bound on the number of triangulations of a planar point setJournal of Combinatorial Theory, Series A, 2003
- Lower bounds on the number of crossing-free subgraphs of KNComputational Geometry, 2000
- The path of a triangulation1999
- Enumerative Combinatorics1999
- A Pattern of Asymptotic Vertex Valency Distributions in Planar MapsJournal of Combinatorial Theory, Series B, 1999
- On the mixing rate of the triangulation walk1998
- Note – On the Number of Triangulations of Planar Point SetsCombinatorica, 1998
- The Four-Colour TheoremJournal of Combinatorial Theory, Series B, 1997
- A Census of Planar TriangulationsCanadian Journal of Mathematics, 1962