2020/07/30 by Manfred Scheucher, Scheucher, Manfred
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #cs.CG #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.2007.15334
openalex publication_date 2020/07/30 · arxiv created 2021/03/11 · arxiv updated 2021/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two labeled point configurations \p1,…,pn\ and \q1,…,qn\ are of the same order type if, for every i,j,k, the triples (pi,pj,pk) and (qi,qj,qk) have the same orientation. In the 1980's, Goodman, Pollack and Sturmfels showed that (i) the number of order types on n points is of order 4n+o(n), (ii) all order types can be realized with double-exponential integer coordinates, and that (iii) certain order types indeed require double-exponential integer coordinates. In 2018, Caraballo, Díaz-Báñez, Fabila-Monroy, Hidalgo-Toscano, Leaños, Montejano showed that at least n3n+o(n) order types can be realized on an integer grid of polynomial size. In this article, we improve their result by showing that at least n4n+o(n) order types can be realized on an integer grid of polynomial size, which is essentially best possible.