Wednesday, January 11th, 2017 16:10
Schreiber 309

Breaking depth-order cycles and other adventures in 3D
Boris Aronov, New York University
Abstract:
I have two topics to present. I spend some time on the first one and
talk about the second one if I have time.
I: Given a collection of non-vertical lines in general position in 3D,
there is a natural "above/below" relation defined on the lines. One
line is above another if the unique vertical line that meets both
meets the former at a point above the point where it meets the later.
One can similarly define the (partial) above/below relation on any set of
reasonably well-behaved pairwise disjoint objects; a pair of objects
is not related at all, if no vertical line meets both.
Motivated by a computer graphics problem, the following question
was asked more than 35 years ago: What is the minimum number of pieces
one must cut N lines into, in the worst case, to make sure that the
resulting pieces have no cycles in their above/below relation? An N^2
upper bound is easy, but is the answer sub-quadratic? An
approximately N^{3/2} lower bound was known, but there were no
non-trivial upper bounds, in general case. Restricted versions of the
problem have been studied and will be briefly discussed. We present a
near-optimal near-N^{3/2} upper bound.
We also sketch how to extend this to the original motivating question
for computer graphics, which until now was unreachable: How many
pieces does one have to cut N triangles into, to eliminate all
cycles in the above/below relationship, as above? We obtain a
near-N^{3/2} bound in this case as well, though slightly weaker.
Joint work with Micha Sharir, and also with Edward Y Miller, for the
extension to triangles.
II: A question motivated by motion planning, generalized Voronoi
diagrams, and a number of related problems was asked some years ago by
Aronov and Sharir: Is it true that the complement of the union of a
collection of N translates of a single convex set in 3D has O(N^2)
connected components? This was phrased as a conjecture and was
recently disproven in a fairly spectacular way. The maximum possible
number of connected components is in fact Omega(N^3) in the worst case
(and it's not hard to see that that's the best possible).
I will explain why the conjecture was not entirely unnatural and
point out its connection to several related problems.
I will the attempt to _show_ the construction. It's essentially a
sequence of not-so-easy to visualize pictures. No one made a movie of
this, as far as I know. The audience is welcome to volunteer to help
make a movie.
Joint work with Michael G. Dobbins (who obtained the construction),
Otfried Cheong and Xavier Goaoc (who worked **really hard** on making
the construction understandable).