2012/03/28 by Oliver Roche‐Newton, Oliver Roche-Newton, Roche-Newton, Oliver +2 · 2 citations
Computer Science · Mathematics · #11B75 #68R05 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Number Theory (math.NT) #Point processes and geometric inequalities #math.CO #math.NT #msc:11B75 #msc:68R05
paper · pdf · doi:10.48550/arxiv.1203.6237
16pp. This is a new extended version of the paper. The previous one had a small gap in the part of the proof, dealing with rich planes, which has been corrected
openalex publication_date 2012/03/28 · arxiv created 2013/03/14 · arxiv updated 2013/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two points p,q in the real plane, the signed area of the rectangle with the diagonal [pq] equals the square of the Minkowski distance between the points p,q. We prove that N>1 points in the Minkowski plane \R1,1 generate Ω(\fracNlogN) distinct distances, or all the distances are zero. The proof follows the lines of the Elekes/Sharir/Guth/Katz approach to the Erd\H os distance problem, analysing the 3D incidence problem, arising by considering the action of the Minkowski isometry group ISO^*(1,1). The signature of the metric creates an obstacle to applying the Guth/Katz incidence theorem to the 3D problem at hand, since one may encounter a high count of congruent line intervals, lying on null lines, or "light cones", all these intervals having zero Minkowski length. In terms of the Guth/Katz theorem, its condition of the non-existence of "rich planes" generally gets violated. It turns out, however, that one can efficiently identify and discount incidences, corresponding to null intervals and devise a counting strategy, where the rich planes condition happens to be just ample enough for the strategy to succeed. As a corollary we establish the following near-optimal sum-product type estimate for finite sets A,B⊂ \R, with more than one element: |(A±B)⋅(A±B)|≫\frac|A||B|log|A|+log|B|.