Home Bookmarks Papers Blog

On the Number of Incidences When Avoiding the Klan

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\BS}{\mathcal{O}}% \newcommand{\P}{P} \newcommand{\Mh}[1]{#1}% \newcommand{\obj}{o}% \newcommand{\p}{p} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$
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