A276096 a(n) is the least number of empty convex pentagons ("convex 5-holes") spanned by a set of n points in the Euclidean plane in general position (i.e., no three points on a line).

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 6, 9, 11

Offset: 1

Author

Manfred Scheucher, Aug 18 2016

Keywords

• nonn
• more

Comments

The value a(10) = 1 was determined by Harborth, who also constructed a set of 9 points without convex 5-holes. The values a(11) = 2 and a(13) = 3 were determined by Dehnhardt. Aichholzer found point sets showing that a(14) <= 6 and a(15) <= 9, and the exact values a(13) = 3, a(14) = 6, and a(15) = 9 were determined in the Bachelor's thesis of Scheucher, supervised by Aichholzer and Hackl.

The value a(16) = 11 was determined using a ILP/SAT solver. For more information check out the link below with title "On 5-Holes". - Manfred Scheucher, Aug 18 2018

References

• K. Dehnhardt, Leere konvexe Vielecke in ebenen Punktmengen, PhD thesis, TU Braunschweig, Germany, 1987, in German.

Links

• O. Aichholzer, M. Balko, T. Hackl, J. Kynčl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber, A superlinear lower bound on the number of 5-holes, arXiv:1703.05253 [math.CO], 2017.
• O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, A. Pilz, and B. Vogtenhuber, Lower bounds for the number of small convex k-holes, Computational Geometry: Theory and Applications, 47(5):605-613, 2014.
• EuroGIGA - CRP ComPoSe, A set of 13 points with 3 convex 5-holes
• EuroGIGA - CRP ComPoSe, A set of 14 points with 6 convex 5-holes
• EuroGIGA - CRP ComPoSe, A set of 15 points with 9 convex 5-holes
• EuroGIGA - CRP ComPoSe, A set of 16 points with 11 convex 5-holes
• H. Harborth, Konvexe Fünfecke in ebenen Punktmengen, Elemente der Mathematik, 33:116-118, 1978, in German.
• M. Scheucher, Counting Convex 5-Holes, Bachelor's thesis, Graz University of Technology, Austria, 2013, in German.
• M. Scheucher, On 5-Holes.

Crossrefs

Cf. A063541 and A063542 for convex 3- and 4-holes, respectively.

Cf. A006247 and A063666 for equivalence classes (w.r.t. orientation triples) of point sets in the plane.

Formula

From Manfred Scheucher, Mar 22 2017: (Start)

a(n) = Omega(n log^(4/5)(n)) and a(n) = O(n^2).

Conjecture: a(n) = Theta(n^2). (End)

Extensions

a(16) from Manfred Scheucher, Mar 22 2017