Many Order Types on Integer Grids of Polynomial Size
share
Two point configurations {p_1,…,p_n} and {q_1,…,q_n} are of the same order type if, for every i,j,k, the triples (p_i,p_j,p_k) and (q_i,q_j,q_k) 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 4^n+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 n^3n-o(n) order types can be realized on an integer grid of polynomial size. In this article, we show that n^4n-o(n) order types can be realized on an integer grid of polynomial size, which is essentially best-possible.
READ FULL TEXT