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

2018/11/06 by Luis E. Caraballo, Caraballo, Luis E., José-Miguel Díaz-Báñez +9
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.CO

paper · pdf · doi:10.48550/arxiv.1811.02455

arxiv created 2018/11/16 · arxiv updated 2018/11/19

Abstract

Let \p₁,…,p_n\ and \q₁,…,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

Related

• Many Order Types on Integer Grids of Polynomial Size
• Smoothed Analysis of Order Types
• Limits of Order Types
• Points below a parabola in affine planes of prime order
• Inscribable order types