A063544 Smallest number of triangulations of n points in the plane.

1, 1, 2, 4, 11, 30, 89, 250, 776, 2236, 7147, 20979, 68448

Offset

3,3

Comments

In a so-called double circle, half of the points are extremal, and for every edge of the convex hull, there is one interior point that is arbitrarily close to it. The double circles are conjectured to minimize the number of triangulations, and in this case the next terms would be 203748, 674949, 2031054, 6807382, 20662980, ... - Manfred Scheucher, Aug 22 2016

References

P. Brass, W. O. J. Moser, J. Pach, Research Problems in Discrete Geometry, Springer (2005).

Links

Table of n, a(n) for n=3..15.

O. Aichholzer, V. Alvarez, T. Hackl, A. Pilz, B. Speckmann and B. Vogtenhuber, An Improved Lower Bound on the Minimum Number of Triangulations, in Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), pages 7:1--7:16, LIPIcs, 2016.

O. Aichholzer, F. Hurtado, and M. Noy, On the Number of Triangulations Every Planar Point Set Must Have, Proceedings of the 13th Annual Canadian Conference on Computational Geometry CCCG 2001, pages 13-16, Waterloo, Ontario, Canada, 2001. See also the Counting Triangulations - Olympics

O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.

F. Santos and R. Seidel, A better upper bound on the number of triangulations of a planar point set, Journal of Combinatorial Theory, Series A, 102(1):186-193, 2003.

EuroGIGA - CRP ComPoSe, Double Circle

Formula

Conjecture: a(n) = sqrt(12)^(n-Theta(log n)). - Manfred Scheucher, Aug 22 2016

Crossrefs

Cf. A063545, A063666.

Sequence in context: A193062 A193061 A193060 * A276145 A148150 A219232

Adjacent sequences: A063541 A063542 A063543 * A063545 A063546 A063547

Keyword

nonn,nice,hard,more

Author

N. J. A. Sloane, Aug 14 2001

Extensions

a(11)-a(15) from Manfred Scheucher, Aug 22 2016

Status

approved