A063541 -id:A063541 - cp's OEIS frontend

A063542 Least number of empty convex quadrilaterals (4-gons) determined by n points in the plane.

0, 1, 3, 6, 10, 15, 23, 32, 42, 51

Offset: 4

N. J. A. Sloane, Aug 14 2001

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

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.
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.
O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, A. Pilz, B. Vogtenhuber, A set of 12 points minimizing the numbers of convex 3-, 4-, and 5-holes.
O. Aichholzer, T. Hackl, and M. Scheucher, A set of 13 points minimizing the numbers of convex 3-, 4-, and 5-holes.
M. Scheucher, Counting Convex 5-Holes, Bachelor's thesis, Graz University of Technology, Austria, 2013, in German.

Cf. A063541 and A276096 for empty convex 3- and 5-gons (a.k.a. k-holes), respectively. The rectilinear crossing number A014540 is the number of (not necessarily empty) convex quadrilaterals.

a(11)-a(13) from Manfred Scheucher, Aug 17 2018

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).

Original entry on oeis.org

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

Offset: 1

Manfred Scheucher, Aug 18 2016

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

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

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.

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.

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)

a(16) from Manfred Scheucher, Mar 22 2017

cp's OEIS Frontend

A063542 Least number of empty convex quadrilaterals (4-gons) determined by n points in the plane.

Views

Author

Keywords

References

Links

Crossrefs

Extensions