Breaking depth-order cycles and other adventures in 3D

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).