On lines, joints, and incidences in three dimensions |
| |
Authors: | György Elekes Haim Kaplan |
| |
Institution: | a Department of Computer Science, Eötvös University, H-1117 Budapest, Hungary b School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel c Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA |
| |
Abstract: | We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz (2010) 9], to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between n lines in R3 and m of their joints (points incident to at least three non-coplanar lines) is Θ(m1/3n) for m?n, and Θ(m2/3n2/3+m+n) for m?n. (ii) In particular, the number of such incidences cannot exceed O(n3/2). (iii) The bound in (i) also holds for incidences between n lines and m arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound O(n3/2), established by Guth and Katz, on the number of joints in a set of n lines in R3. We also present some further extensions of these bounds, and give a trivial proof of Bourgain's conjecture on incidences between points and lines in 3-space, which is an immediate consequence of our incidence bounds, and which constitutes a much simpler alternative to the proof of Guth and Katz (2010) 9]. |
| |
Keywords: | Lines in 3-space Joints Incidences Algebraic techniques Polynomials |
本文献已被 ScienceDirect 等数据库收录! |
|