Paper

## Point–Line Incidences in Space

MICHA SHARIR a1a2 1 and EMO WELZL a3 2
a1 School of Computer Science, Tel Aviv University, Tel-Aviv 69978, Israel
a2 Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: sharir@cs.tau.ac.il)
a3 Institut für Theoretische Informatik, ETH Zürich, CH-8092 Zürich, Switzerland (e-mail: emo@inf.ethz.ch)

## Abstract

Given a set $L$ of $n$ lines in ${\mathbb R}^3$, joints are points in ${\mathbb R}^3$ that are incident to at least three non-coplanar lines in $L$. We show that there are at most $O(n^{5/3})$ incidences between $L$ and the set of its joints.

This result leads to related questions about incidences between $L$ and a set $P$ of $m$ points in ${\mathbb R}^3$. First, we associate with every point $p \in P$ the minimum number of planes it takes to cover all lines incident to $p$. Then the sum of these numbers is at most $O\big(m^{4/7}n^{5/7}+m+n\big).$ Second, if each line forms a fixed given non-zero angle with the $xy$-plane – we say the lines are equally inclined – then the number of (real) incidences is at most $O\big(\min\big\{m^{3/4}n^{1/2}\kappa(m),\ m^{4/7}n^{5/7}\big\} + m + n\big) ,$ where $\kappa(m) \,{=}\, (\log m)^{O(\alpha^2(m))}$, and $\alpha(m)$ is the slowly growing inverse Ackermann function. These bounds are smaller than the tight Szemerédi–Trotter bound for point–line incidences in $\reals^2$, unless both bounds are linear. They are the first results of this type on incidences between points and $1$-dimensional objects in $\reals^3$. This research was stimulated by a question raised by G. Elekes.

(Published Online March 3 2004)