Counting triangulations of planar point sets (Q540059)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting triangulations of planar point sets |
scientific article |
Statements
Counting triangulations of planar point sets (English)
0 references
1 June 2011
0 references
Summary: We study the maximal number of triangulations that a planar set of \(n\) points can have, and show that it is at most \(30n\). This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl, which has led to the previous best upper bound of \(43n\) for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, it can be used to derive new upper bounds for the number of planar graphs \((207.84n)\), spanning cycles \((O(68.67n))\), spanning trees \((O(146.69n))\), and cycle-free graphs \((O(164.17n))\).
0 references
triangulations
0 references
counting
0 references
charging schemes
0 references
crossing-free graphs
0 references