Many Order Types on Integer Grids of Polynomial Size

Manfred Scheucher

Published 2020-07-30Version 1

Two point configurations $\{p_1,\ldots,p_n\}$ and $\{q_1,\ldots,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\'iaz-B\'a{\~n}ez, Fabila-Monroy, Hidalgo-Toscano, Lea{\~n}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.