Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
| Autor: | Esther Ezra, Boris Aronov, Joshua Zahl |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Discrete mathematics Polynomial General Computer Science General Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Constructive Set (abstract data type) Integer 010201 computation theory & mathematics Bounded function Computer Science - Computational Geometry Algebraic curve 0101 mathematics Depth order Mathematics |
| Zdroj: | SIAM Journal on Computing. 49:1109-1127 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/19m1257548 |
| Popis: | 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+\epsilon})$ pieces that are depth-cycle free, for any $\epsilon > 0$. The algorithm runs in $O(n^{3/2+\epsilon})$ time, which is a considerable improvement over the previously known algorithms. Comment: 20 pages, 0 figures. v2: final version, to appear in SIAM J. Comput. A preliminary version of this work was presented in Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms, 2019 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|