Combinatorics, Probability and Computing


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:
a3 Institut für Theoretische Informatik, ETH Zürich, CH-8092 Zürich, Switzerland (e-mail:

Article author query
sharir m   [Google Scholar] 
welzl e   [Google Scholar] 


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)
(Received July 2 2002)
(Revised April 12 2003)


1 Work on this paper by Micha Sharir was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the US–Israeli Binational Science Foundation, by a grant from the Israel Science Fund (for a Center of Excellence in Geometric Computing), and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Part of the work was done when Micha Sharir visited ETH Zürich in the Spring of 2001.

2 A preliminary version of this paper appeared in Proc. 18th Ann. ACM Symp. on Comput. Geometry (2002), pp. 107–115.