Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2019
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908755719880704 |
|---|---|
| author | Aronov, Boris Ezra, Esther Zahl, Joshua |
| author_facet | Aronov, Boris Ezra, Esther Zahl, Joshua |
| contents | In 2015, Guth proved that for any set of $k$-dimensional bounded complexity varieties in $\mathbb{R}^d$ and for any positive integer $D$, there exists a polynomial of degree at most $D$ whose zero set divides $\mathbb{R}^d$ into open connected sets, so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz for points.
Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for $k>0$, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in $\mathbb{R}^3$.
We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$, we efficiently construct a decomposition of space into $O(D^3\log^3{D})$ open "cells," each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$. For the case of lines in $3$-space we present an improved implementation, whose running time is $O(n^{4/3} \log^{O(1)} n)$. The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves.
As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in $3$-space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts $n$ such lines into $O(n^{3/2+ε})$ pieces that are depth-cycle free, for any $ε> 0$. The algorithm runs in $O(n^{3/2+ε})$ time, which is a considerable improvement over the previously known algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1904_09526 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications Aronov, Boris Ezra, Esther Zahl, Joshua Computational Geometry In 2015, Guth proved that for any set of $k$-dimensional bounded complexity varieties in $\mathbb{R}^d$ and for any positive integer $D$, there exists a polynomial of degree at most $D$ whose zero set divides $\mathbb{R}^d$ into open connected sets, so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for $k>0$, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in $\mathbb{R}^3$. We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$, we efficiently construct a decomposition of space into $O(D^3\log^3{D})$ open "cells," each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$. For the case of lines in $3$-space we present an improved implementation, whose running time is $O(n^{4/3} \log^{O(1)} n)$. The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in $3$-space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts $n$ such lines into $O(n^{3/2+ε})$ pieces that are depth-cycle free, for any $ε> 0$. The algorithm runs in $O(n^{3/2+ε})$ time, which is a considerable improvement over the previously known algorithms. |
| title | Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/1904.09526 |