On the Number of Incidences when Avoiding the Klan
share
Given a set of points P and a set of regions 𝒪, an incidence is a pair (p,o ) ∈ P ×𝒪 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 K_k,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 log^d 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.
READ FULL TEXT