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

Abstract Let { p 1 , … , p n } and { q 1 , … , 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 size.