A063666 -id:A063666 - cp's OEIS frontend

A006248 Number of projective pseudo order types: simple arrangements of pseudo-lines in the projective plane.

1, 1, 1, 1, 1, 4, 11, 135, 4382, 312356, 41848591, 10320613331

Offset: 1

J. Bokowski, personal communication.
J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 102.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Bokowski & N. J. A. Sloane, Emails, June 1994
F. Cortés Kühnast, J. Dallant, S. Felsner, and M. Scheucher, An Improved Lower Bound on the Number of Pseudoline Arrangements
Stefan Felsner and Jacob E. Goodman, Pseudoline Arrangements, Chapter 5 of Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [Specific reference for this sequence] - _N. J. A. Sloane_, Nov 14 2023
S. Felsner and J. E. Goodman, Pseudoline Arrangements. In: Toth, O'Rourke, Goodman (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. CRC Press, 2018.
J. Ferté, V. Pilaud and M. Pocchiola, On the number of simple arrangements of five double pseudolines, arXiv:1009.1575 [cs.CG], 2010; Discrete Comput. Geom. 45 (2011), 279-302.
Lukas Finschi, A Graph Theoretical Approach for Reconstruction and Generation of Oriented Matroids, A dissertation submitted to the Swiss Federal Institute of Technology, Zurich for the degree of Doctor of Mathematics, 2001.
L. Finschi, Homepage of Oriented Matroids
L. Finschi and K. Fukuda, Complete combinatorial generation of small point set configurations and hyperplane arrangements, pp. 97-100 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.
Komei Fukuda, Hiroyuki Miyata, and Sonoko Moriyama, Complete Enumeration of Small Realizable Oriented Matroids, arXiv:1204.0645 [math.CO], 2012; Discrete Comput. Geom. 49 (2013), no. 2, 359--381. MR3017917. - From _N. J. A. Sloane_, Feb 16 2013
Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [General reference for 2017 edition of the Handbook] - _N. J. A. Sloane_, Nov 14 2023
D. E. Knuth, Axioms and Hulls, Lect. Notes Comp. Sci., Vol. 606, Springer-Verlag, Berlin, Heidelberg, 1992, p.35, entry E_n.
Index entries for sequences related to sorting

Cf. A006245, A006246, A018242, A063666. A diagonal of A063851.

Asymptotics: 2^{Cn^2} <= a(n) <= 2^{Dn^2} for every n >= N, where N,C,D are constants with 0.1887Manfred Scheucher, Apr 10 2025 on personal communication with Günter Rote.]

a(11) from Franz Aurenhammer (auren(AT)igi.tu-graz.ac.at), Feb 05 2002
a(12) from Manfred Scheucher and Günter Rote, Sep 07 2019
Definition corrected by Günter Rote, Dec 01 2021

A006247 Number of simple arrangements of n pseudolines in the projective plane with a marked cell. Number of Euclidean pseudo-order types: nondegenerate abstract order types of configurations of n points in the plane.

Original entry on oeis.org

1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538

Offset: 1

N. J. A. Sloane

Also the number of nonisomorphic nondegenerate acyclic rank 3 oriented matroids on n elements. - Manfred Scheucher, May 09 2022

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

O. Aichholzer, Order Types for Small Point Sets
O. Aichholzer, F. Aurenhammer and H. Krasser, Enumerating order types for small point sets with applications, In Proc. 17th Ann. ACM Symp. Computational Geometry, pages 11-18, Medford, Massachusetts, USA, 2001. [Computes a(10)]
Stefan Felsner and Jacob E. Goodman, Pseudoline Arrangements, Chapter 5 of Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [Specific reference for this sequence] - _N. J. A. Sloane_, Nov 14 2023
J. Ferté, V. Pilaud and M. Pocchiola, On the number of simple arrangements of five double pseudolines, arXiv:1009.1575 [cs.CG], 2010; Discrete Comput. Geom. 45 (2011), 279-302.
Lukas Finschi, A Graph Theoretical Approach for Reconstruction and Generation of Oriented Matroids, A dissertation submitted to the Swiss Federal Institute of Technology, Zurich for the degree of Doctor of Mathematics, 2001.
Lukas Finschi, Homepage of Oriented Matroids
L. Finschi and K. Fukuda, Complete combinatorial generation of small point set configurations and hyperplane arrangements, pp. 97-100 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.
Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, and Birgit Vogtenhuber, Geometric Thickness of Multigraphs is (exists in reals)-complete, arXiv:2312.05010 [cs.CG], 2023.
Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry [alternative link], CRC Press, 2017, see Table 5.6.1. [General reference for 2017 edition of the Handbook] - _N. J. A. Sloane_, Nov 14 2023
J. E. Goodman and R. Pollack, Semispaces of configurations, cell complexes of arrangements, J. Combin. Theory, A 37 (1984), 257-293.
D. E. Knuth, Axioms and hulls, Lect. Notes Comp. Sci., Vol. 606.
Alexander Pilz and Emo Welzl, Order on order types, Discrete & Computational Geometry, 59 (No. 4, 2015), 886-922.
Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner, A Note On Universal Point Sets for Planar Graphs, arXiv:1811.06482 [math.CO], 2018.

Cf. A006248, A014540, A063852, A063666, A325595, A325628, A006245

Asymptotics: a(n) = 2^(Theta(n^2)). This is Bachmann-Landau notation, that is, there are constants n_0, c, and d, such that for every n >= n_0 the inequality 2^{c n^2} <= a(n) <= 2^{d n^2} is satisfied. For more information see e.g. the Handbook of Discrete and Computational Geometry. - Manfred Scheucher, Sep 12 2019

a(11) from Franz Aurenhammer (auren(AT)igi.tu-graz.ac.at), Feb 05 2002
a(12) from Manfred Scheucher and Günter Rote, Aug 31 2019
a(13) from Manfred Scheucher and Günter Rote, Sep 12 2019
Definition clarified by Manfred Scheucher, Jun 22 2023

A018242 Number of projective order types.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 4, 11, 135, 4381, 312114, 41693377

Offset: 0

N. J. A. Sloane

Table 5.6.1 in the Felsner-Goodman survey contains this sequence in the second row, but the line is incorrectly labeled. The origin of these data is the paper of Aichholzer and Krasser. - Günter Rote, Apr 16 2025

Oswin Aichholzer, Hannes Krasser: Abstract order type extension and new results on the rectilinear crossing number. Comput. Geom. 36(1), 2-15 (2007), Table 1
Stefan Felsner and Jacob E. Goodman, Pseudoline Arrangements, Chapter 5 of Handbook of Discrete and Computational Geometry, 3rd edition, Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, CRC Press, 2017, see Table 5.6.1. [alternative link][alternative link] [Specific reference for this sequence] - N. J. A. Sloane, Nov 14 2023
Komei Fukuda, Hiroyuki Miyata, Sonoko Moriyama, Complete Enumeration of Small Realizable Oriented Matroids. Discrete Comput. Geom. 49 (2013), no. 2, 359-381, see Table 2. MR3017917. Also arXiv:1204.0645 [math.CO], 2012. - From _N. J. A. Sloane_, Feb 16 2013

Cf. A006247, A006248, A063666. A diagonal of A222317.

Asymptotics: a(n) = 2^(Theta(n log n)). This is Bachmann-Landau notation, that is, there are constants n_0, c, and d, such that for every n >= n_0 the inequality 2^(c n log n) <= a(n) <= 2^(d n log n) is satisfied. For more information see e.g. the Handbook of Discrete and Computational Geometry. - Manfred Scheucher, Sep 12 2019

a(11) from Franz Aurenhammer (auren(AT)igi.tu-graz.ac.at), Feb 05 2002

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

Original entry on oeis.org

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

Offset: 3

N. J. A. Sloane, Aug 14 2001

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

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

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

Cf. A063545, A063666.

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

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

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

A276110 The number of rotation systems of drawings of the complete graph K_n, where the rotation system describes the clockwise cyclic order of incident edges around each vertex.

Original entry on oeis.org

1, 2, 5, 102, 11556, 5370725, 7198391729

Offset: 3

Manfred Scheucher, Aug 18 2016

The number of realizable order types on n points in the plane (A063666) is exactly the number of rotation systems of straight-line drawings of K_n.

B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, T. Hackl, J. Pammer, A. Pilz, P. Ramos, G. Salazar, and B. Vogtenhuber, All Good Drawings of Small Complete Graphs, In Proc. 31st European Workshop on Computational Geometry EuroCG '15, pages 57-60, Ljubljana, Slovenia, 2015.
A. Arroyo, D. McQuillan, and B. Richter, Drawings of Kn with the same rotation scheme are the same up to Reidemeister moves (Gioan's Theorem), submitted, 2015.
J. Kynčl, Enumeration of simple complete topological graphs, European Journal of Combinatorics, 30(7):1676-1685, 2009.
Wikipedia, Rotation Systems

Coincides with A276109 for n <= 5.

Cf. A000241, A063666.

A373222 Number of labeled orientations of n points on an Euclidean plane, in general position. In other words, the number of all possible orientation of n points in general position if all points are distinct and are labeled from 1 to n.

Original entry on oeis.org

2, 14, 264, 11904, 1198560, 257847120

Offset: 3

Jihoon Hyun, May 28 2024

For non-indexed version, see A063666.

a(n) ~ 2^(Theta(n log n)).

Cf. A063666.

cp's OEIS Frontend

A006248 Number of projective pseudo order types: simple arrangements of pseudo-lines in the projective plane.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A006247 Number of simple arrangements of n pseudolines in the projective plane with a marked cell. Number of Euclidean pseudo-order types: nondegenerate abstract order types of configurations of n points in the plane.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A018242 Number of projective order types.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A276110 The number of rotation systems of drawings of the complete graph K_n, where the rotation system describes the clockwise cyclic order of incident edges around each vertex.

Views

Author

Keywords

Comments

Links

Crossrefs

A373222 Number of labeled orientations of n points on an Euclidean plane, in general position. In other words, the number of all possible orientation of n points in general position if all points are distinct and are labeled from 1 to n.

Views

Author

Keywords

Comments

Crossrefs