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

Author

N. J. A. Sloane, Aug 14 2001

Keywords

• nonn
• nice
• hard
• more

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

• 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

Crossrefs

Cf. A063545, A063666.

Formula

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

Extensions

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