论文标题
多项式大小的整数网格上的许多订单类型
Many Order Types on Integer Grids of Polynomial Size
论文作者
论文摘要
Two labeled 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. 2018年，Caraballo，Díaz-Bá{ñ} ez，Fabila-Monroy，Hidalgo-Toscano，Lea {ñ} OS，Montejano表明，至少$ n^{3n+o（n）} $订单类型可以在多项式大小的integer Grid上实现。在本文中，我们通过表明至少可以在多项式大小的整数网格上实现$ n^{4n+o（n）} $订单类型来改善他们的结果，这实际上是最好的。
Two labeled 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íaz-Bá{ñ}ez, Fabila-Monroy, Hidalgo-Toscano, Lea{ñ}os, Montejano showed that at least $n^{3n+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 $n^{4n+o(n)}$ order types can be realized on an integer grid of polynomial size, which is essentially best possible.
