Personal tools
You are here: Home CG seminar 2018 Constructive Polynomial Partitioning for Lines in~$\reals^3$: Revisiting Depth Cycle Elimination
« June 2018 »
June
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

Constructive Polynomial Partitioning for Lines in~$\reals^3$: Revisiting Depth Cycle Elimination

Wednesday, April 11th, 2018, 16:10

Schreiber 309

underline

Constructive Polynomial Partitioning for Lines in~$\reals^3$: Revisiting Depth Cycle Elimination

Esther Ezra, Bar-Ilan University

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 obtain an explicit representation of such a partitioning polynomial (and how to construct it efficiently). 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, under the assumption that the lines are non-vertical and pairwise disjoint. 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 this combinatorial bound. 
 
Joint work with Boris Aronov.
Document Actions