On the use of Klein quadric for geometric incidence problems in two dimensions

Misha Rudnev, J. M. Selig

Research output: Contribution to journalArticle (Academic Journal)peer-review

8 Citations (Scopus)
386 Downloads (Pure)

Abstract

We discuss a unified approach to a class of geometric combinatorics incidence problems in $2D$, of the Erdös distance type. The goal is obtaining the second moment estimate, that is given a finite point set $S$ and a function $f$ on $S\times S$, an upper bound on the number of solutions of $$ f(p,p') = f(q,q')\neq 0,\qquad (p,p',q,q')\in S\times S\times S\times S. \qquad(*) $$ E.g., $f$ is the Euclidean distance in the plane, sphere, or a sheet of the two-sheeted hyperboloid. Our tool is the Guth-Katz incidence theorem for lines in $\mathbb{RP}^3$, but we focus on how the original $2D$ problem is made amenable to it. This procedure was initiated by Elekes and Sharir, based on symmetry considerations. However, symmetry considerations can be bypassed or made implicit. The classical Plücker-Klein formalism for line geometry enables one to directly interpret a solution of $(*)$ as intersection of two lines in $\mathbb{RP}^3$. This allows for a very brief argument extending the Euclidean plane distance argument to the spherical and hyperbolic distances. We also find instances of the question $(*)$ without underlying symmetry group. The space of lines in the three-space, the Klein quadric $\mathcal K$, is four-dimensional. We start out with an injective map $\mathfrak F:\,S\times S\to\mathcal K$, from a pair of points in $2D$ to a line in $3D$ and seek a combinatorial problem in the form $(*)$, which can be solved by applying the Guth-Katz theorem to the set of lines in question. We identify a few new such problems and generalise the existing ones.
Original languageEnglish
Pages (from-to)934-954
Number of pages21
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number2
Early online date12 May 2016
DOIs
Publication statusPublished - Jun 2016

Bibliographical note

Theorem 5', implicit in the earlier verisons has been stated explicitly in this ArXiv version, giving a family of applications of the Guth-Katz theorem to sum-product type quantities, with no underlying symmetry group

Keywords

  • math.MG
  • math.CO
  • 68R05, 11B75

Fingerprint Dive into the research topics of 'On the use of Klein quadric for geometric incidence problems in two dimensions'. Together they form a unique fingerprint.

Cite this