Micha Sharir: Eliminating depth cycles and its relatives

Abstract: The basis for the talk is 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 30-year old problem asks for a sharp upper bound on the number of such cuts. After briefly mentioning older approaches, based on weaving patterns of lines, 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}). (Joint work with Boris Aronov.) We then present a variety of related recent works: (a) We show that a similar approach yields a method for eliminating depth cycles in a set of pairwise disjoint triangles in 3-space. (This is the "real" problem that arises in applications to computer graphics.) (Joint work with Boris Aronov and Ed Miller.) (b) We discuss efficient algorithmic implementations of these techniques, covering results by Mark de Berg and by Boris Aronov, Esther Ezra, and Josh Zahl. (c) We give a surprising application of the technique for eliminating lenses in arrangements of n algebraic arcs in the plane, which in turn shows that the arcs can be cut into roughly n^{3/2} arcs, each pair of which intersect at most once. This leads to improved incidence bounds between points and curves in the plane. (Joint work with Josh Zahl.) (d) Finally, we touch upon a recent application of the technique, due to Zahl, of eliminating cycles in four dimensions, with applications to bounding the number of unit distances in three dimensions.