On the Number of Order Types in Integer Grids of Small Size

Luis E. Caraballo, José-Miguel Díaz-Báñez, Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Jesús Leaños, Amanda Montejano

Published 2018-11-06Version 1

Let $\{p_1,\dots,p_n\}$ and $\{q_1,\dots,q_n\}$ be two sets of $n$ labeled points in general position in the plane. We say that these two point sets have the same order type if for every triple of indices $(i,j,k)$, $p_k$ is above the directed line from $p_i$ to $p_j$ if and only if $q_k$ is above the directed line from $q_i$ to $q_j$. In this paper we give the first non-trivial lower bounds on the number of different order types of $n$ points that can be realized in integer grids of polynomial