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