Home | Bookmarks | Papers | Blog |

Timothy M. Chan and Sariel Har-Peled.

Given a set of points $\P$ and a set of regions $\BS$, an \emph{incidence} is a pair $(\p,\obj ) \in \P \times \BS$ such that $\p \in \obj$. 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\bigl( k n(\log n/\log\log n)^{d-1} \bigr)$ on the number of incidences between $n$ points and $n$ axis-parallel boxes in $\Re^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.

PDF : arXiv.

Last modified: Sat 2022-07-23 21:02:43 UTC 2022 by Sariel Har-Peled