Speaker: Micha Sharir (Tel Aviv University)
Title: Eliminating depth cycles for lines and triangles, with applications to bounding incidences
Abstract:
---------
The talk presents three related results.
We first consider the problem of eliminating all depth cycles in a set of n lines in 3-space.
For two lines l_1, l_2 in 3-space (in general position), we say that l_1 lies below l_2 if the
unique vertical line that meets both lines meets l_1 at a point below the point where it meets l_2.
This depth relationship typically has cycles, which can be eliminated if we cut the lines into
smaller pieces. A 25-year old problem asks for a sharp upper bound on the number of such cuts.
We show that this can be done with O(n^{3/2} polylog(n)) cuts, almost meeting the known worst-case
lower bound Omega(n^{3/2}).
The second topic extends the previous result to eliminating depth cycles in a set of pairwise
disjoint triangles in 3-space. (This is the "real" problem one would like to solve, motivated
by applications to computer graphics.) The depth relationship is defined in an analogous manner,
and cycles can be eliminated by cutting the triangles into simply-shaped pieces for which the
depth relationship is acyclic. A well known (albeit non-trivial) way of doing this is to use
a binary space partition, which produces quadratically many cuts (into triangular pieces).
We extend the cycle elimination result for lines to this setup, and show that all depth cycles
can be eliminated by cutting the triangles into O(n^{3/2+eps}) pieces, for any eps>0, where
each piece is a semialgebraic region of constant complexity (where this complexity depends on eps).
The extension is fairly involved, as it needs to use fairly sophisticated topological arguments
(unnecessary for the case of lines) to control the number of pieces.
The third topic is based on a straightforward, albeit technically demanding, extension of the
first result to eliminating cycles in a set of n algebraic arcs of constant degree in 3-space, with
a similar upper bound, close to n^{3/2}, on the number of required cuts. Combining this with a recent
idea of Ellenberg, Solymosi, and Zahl, we obtain new incidence bounds for points and arbitrary
fixed-degree algebraic curves in the plane.
All these developments are based on the polynomial partitioning technique of Guth and Katz, and
constitute a somewhat "unorthodox" application of this tool, which we hope will have follow-up
applications of a similar nature.
Based on joint works with Boris Aronov, Ed Miller, and Joshua Zahl.