On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings

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(kn(logn/loglogn)^d-1) on the number of incidences between n points and n axis-parallel boxes in R^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 et al. (Forum Math Sigma 9:59, 2021), by more than a factor of log^dn for d>2. Furthermore, it matches a lower bound implied by the work of Chazelle (J ACM 37(2):200–212, 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.