2018/10/02 by T. Thao, Do, Thao T.
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1810.01043
openalex publication_date 2018/10/02 · openalex created_date 2018/10/12 · openalex updated_date 2026/07/28
Non-degeneracy was first defined for hyperplanes by Elekes-Tóth, and later extended to spheres by Apfelbaum-Sharir: given a set P of m points in ℝd and some β∈(0,1), a (d-1)-dimensional sphere (or a (d-1)-sphere) S in ℝd is called β-nondegenerate with respect to P if S does not contain a proper subsphere S' such that |S'∩ P|≥ β|S∩ P|. Apfelbaum-Sharir found an upper bound for the number of incidences between points and nondegenerate spheres in three dimensions, which was recently used by Zahl to obtain the best known bound for the unit distance problem in three dimensions. In this paper, we show that the number of incidences between m points and n β-nondegenerate 3-spheres in ℝ4 is Oβ,ε(m(15)/(19)+ε n(16)/(19)+mn(2)/(3)). As a consequence, we obtain a bound of Oε(n2+4/11+ε) on the number of similar triangles formed by n points in ℝ4, an improvement over the previously best known bound O(n2+2/5). While proving this, we find it convenient to work with a more general definition of nondegeneracy: a bipartite graph G=(P,Q) is called β-nondegenerate if |N(q1)∩ N(q2)|