עמוד זה מציג את כל האירועים המתרחשים במחלקה השבוע. ניתן לבחור שבוע אחר, או תאריכים שונים, בשדות בתחתית העמוד.

Combinatorics Seminar

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

מרץ 5, 14:00—15:00, 2018, -101

מרצה

Esther Ezra (Bar Ilan)

תקציר

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.


תאריכים אחרים