This page list all events and seminars that take place in the department this week. Please use the form below to choose a different week or date range.

Combinatorics Seminar

Constructive Polynomial Partitioning for Lines in R^3 and its Applications

Mar 5, 14:00-15:00, 2018, -101

Speaker

Esther Ezra (Bar Ilan)

Abstract

A recent extension of Guth (2015) to the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial, for a given set of $k$-dimensional varieties in ${\reals}^d$, which subdivides space into open cells each of which meeting only a small fraction of the total number of varieties. For most instances, it is unknown how to efficiently obtain an explicit representation of such a partitioning polynomial. This, in particular, applies to the(simple) case of lines in 3-space. In this work we present an efficient algorithmic (but somewhat suboptimal) construction for this setting. We then revisit the problem of eliminating depth cycles among $n$ non-vertical pairwise disjoint triangles in $3$-space, recently been studied by Aronov etal. (2017) and de Berg (2017). Our main result is an algorithmic $O(n^{5/3+\eps})$ bound, for any $\eps > 0$, on the number of pieces one needs to cut the triangles such that the depth relation they induce does not contain cycles. The running time of our algorithm is comparable with the combinatorial bound.

Joint work with Boris Aronov.


Other Dates