Many order types on integer grids of polynomial size (Q2096371)

Two sets of \(n\) labeled points \(P=\{p_1,p_2,\dots,p_n\}\), \(Q=\{q_1,q_2,\dots,q_n\}\) in the plane are of the same labeled 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. They are of the same (unlabeled) order type if there exists a permutation \(\pi:[n]\rightarrow [n]\) such that for every \(i,j,k,\) the triples \((p_i,p_j,p_k)\) and \((q_{\pi(i)},q_{\pi(j)},q_{\pi(k)})\) have the same orientation. An order type in which three or more points lie on a common line is called degenerate. \textit{J. E. Goodman} and \textit{R. Pollack} [SIAM J. Comput. 12, 484--507 (1983; Zbl 0525.68038)] showed that the number of non-degenerate labeled order types on \(n\) points is of order \(\exp(4n\log(n)+O(n))=n^{4n+o(n)}\). Later \textit{J. E. Goodman, R. Pollack} and \textit{B. Sturmfels} in a subsequent paper [``Coordinate representation of order types requires exponential storage'', Proceedings of the twenty-first annual ACM symposium on theory of computing, STOC'89. 405--410 (1989; \url{doi:10.1145/73007.73046})] showed that all non-degenerate order types can be realized with double exponential integer coordinates and that certain order types indeed require double-exponential integer coordinates. Caraballo, Díaz-Báñez, Fabila-Monroy, Hidalgo-Toscano, Leaños, and Montejano [\textit{L. E. Caraballo} et al., Comput. Geom. 95, Article ID 101730, 8 p. (2021; Zbl 07396275)] showed that at least \(n^{3n+o(n)}\) labeled \(n\)-point order types can be realized on an integer grid of polynomial size. In this article, the author improves their result by showing the theorem that the number of non-degenerate labeled \(n\)-point order types which can be realized on an integer grid of size \((3n^4)\times (3n^4)\) is of order \(n^{4n+o(n)}\). While the exponent in \(n^{4n+o(n)}\) bound is asymptotically tight, the question for the smallest constant \(c\), for which \(n^{4n+o(n)}\) labeled order types can be realized on a grid of size \(\Theta(n^c)\times\Theta(n^c)\), remains open. As a corollary to the theorem, the author in this article also obtains the following. The number of non-degenerate (unlabeled) \(n\)-point order types is \(n^{3n+o(n)}\) and \(n^{3n+o(n)}\) of them can be realized on an integer grid of size \((3n^4)\times (3n^4)\).