The Constant of Proportionality in Lower Bound Constructions of Point-Line Incidences

2017/05/31 by Roel Apfelbaum, Apfelbaum, Roel
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #cs.CG #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1706.00091

openalex publication_date 2017/05/31 · openalex created_date 2017/06/09 · arxiv created 2017/07/15 · arxiv updated 2017/07/18 · openalex updated_date 2026/07/28

Abstract

Let I(n,l) denote the maximum possible number of incidences between n points and l lines. It is well known that I(n,l) = Θ(n^2/3l^2/3 + n + l). Let c_SzTr denote the lower bound on the constant of proportionality of the n^2/3l^2/3 term. The known lower bound, due to Elekes, is c_SzTr ≥ 2^-2/3 = 0.63. With a slight modification of Elekes' construction, we show that it can give a better lower bound of c_SzTr ≥ 1, i.e., I(n,l) ≥ n^2/3l^2/3. Furthermore, we analyze a different construction given by Erd\H os, and show its constant of proportionality to be even better, c_SzTr ≥ 3/(2^1/3π^2/3) ≈ 1.11.

Related

• Incidences between points and lines in three dimensions
• The constant of point-line incidence constructions
• Incidences between points on a variety and planes in R³
• Incidences with curves in R^d
• Incidences between points and lines on two- and three-dimensional varieties