Why did it take reading the computational complexity theory column in SIGACT News to find out about this pretty proof in combinatorial Euclidean geometry? It was posted to the combinatorics section of arXiv a little over a year ago but I guess the abstruse title dissuaded me from looking in more depth when it came out; if I'd read the abstract I'm sure I would have remembered it.

Theorem [Guth and Katz, arXiv:0812.1043]: Any system of n lines in three dimensions has \( O(n^{3/2}) \) joints, points where three or more non-coplanar lines meet.

Proof sketch: without loss of generality each line has some constant times the average number of joints on it (otherwise, throw away the lines with too few joints). If there are \( m \) joints, then there exists a nonzero polynomial \( p \) of degree \( O(m^{1/3}) \) that vanishes on all the joints, and if \( m \) is more than \( O(n^{3/2}) \) then this degree would be smaller than the number of joints per remaining line, and the polynomial would vanish on all of the lines. But then one can use the fact that the lines span the space at each joint to show that a lower-degree nonzero polynomial, one of the terms of the gradient of \( p \), also vanishes on the joints, contradicting the existence of a minimum degree for polynomials with this property. QED.

\( O(n^{3/2}) \) is tight, of course, since that's the number of joints for the axis-parallel lines through a cube in an integer grid. The argument generalizes to show that \( n \) lines in \( d \) dimensions have \( O(n^{d/(d-1)}) \) points of intersection such that the lines through these points span the whole space.

I'm not sure what is known for weaker assumptions, e.g. how many points of triple intersection can there be in a system of lines where there is a constant bound on the number of mutually coplanar lines? Then the argument above doesn't work because the lines at any particular triple intersection are allowed to be coplanar. There aren't any interesting bounds if one substitutes "double" for "triple" since one can get quadratically many double intersections from lines on a hyperboloid with no three lines coplanar.

See also: arXiv:0905.1583, arXiv:0906.0555, arXiv:0906.0558.




Comments:

None:
2010-02-21T04:25:13Z

There is a simpler proof by now: http://arxiv.org/abs/0906.0558

Its very nice.

--Sariel

None:
2010-02-21T04:26:03Z

There is a simpler proof by now: http://arxiv.org/abs/0906.0558

Its very nice.

Oh. You mention it in the bottom. silly me.

--Sariel

11011110:
2010-02-21T05:08:55Z

I was a little sloppy in my attributions — the simpification of the proof was the one they ended up describing in the SIGACT News piece (and the one I briefly summarized here).