2021/12/29 by Chan, Timothy M., Har-Peled, Sariel · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2112.14829
openalex publication_date 2021/12/29 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Given a set of points P and a set of regions O, an incidence is a pair (p,o ) ∈ P × O such that p ∈ o. We obtain a number of new results on a classical question in combinatorial geometry: What is the number of incidences (under certain restrictive conditions)? We prove a bound of O( k n(log n/loglog n)d-1 ) on the number of incidences between n points and n axis-parallel boxes in ℝd, if no k boxes contain k common points, that is, if the incidence graph between the points and the boxes does not contain Kk,k as a subgraph. This new bound improves over previous work, by Basit, Chernikov, Starchenko, Tao, and Tran (2021), by more than a factor of logd n for d >2. Furthermore, it matches a lower bound implied by the work of Chazelle (1990), for k=2, thus settling the question for points and boxes. We also study several other variants of the problem. For halfspaces, using shallow cuttings, we get a linear bound in two and three dimensions. We also present linear (or near linear) bounds for shapes with low union complexity, such as pseudodisks and fat triangles.