An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909986040315904 |
|---|---|
| author | Agarwal, Pankaj K. Aronov, Boris Ezra, Esther Zahl, Joshua |
| author_facet | Agarwal, Pankaj K. Aronov, Boris Ezra, Esther Zahl, Joshua |
| contents | In 2015, Guth proved that if $S$ is a collection of $n$ $g$-dimensional semi-algebraic sets in $\mathbb{R}^d$ and if $D\geq 1$ is an integer, then there is a $d$-variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $S$. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently -- the expected running time of our algorithm is linear in $|S|$. Our approach exploits the technique of quantifier elimination combined with that of $ε$-samples. We also present an extension of our construction to multi-level polynomial partitioning for semi-algebraic sets in $\mathbb{R}^d$.
We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+ε})$. The second is a data structure for answering range-searching queries with semi-algebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+ε})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+ε})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudo-segments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$, where we show a nearly-optimal algorithm to cut $n$ pairwise disjoint non-vertical triangles in $\mathbb{R}^3$ into pieces that form a depth order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1812_10269 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications Agarwal, Pankaj K. Aronov, Boris Ezra, Esther Zahl, Joshua Computational Geometry 68Q01, 68W01, 14Q20 F.2.2; I.3.5 In 2015, Guth proved that if $S$ is a collection of $n$ $g$-dimensional semi-algebraic sets in $\mathbb{R}^d$ and if $D\geq 1$ is an integer, then there is a $d$-variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $S$. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently -- the expected running time of our algorithm is linear in $|S|$. Our approach exploits the technique of quantifier elimination combined with that of $ε$-samples. We also present an extension of our construction to multi-level polynomial partitioning for semi-algebraic sets in $\mathbb{R}^d$. We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+ε})$. The second is a data structure for answering range-searching queries with semi-algebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+ε})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+ε})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudo-segments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$, where we show a nearly-optimal algorithm to cut $n$ pairwise disjoint non-vertical triangles in $\mathbb{R}^3$ into pieces that form a depth order. |
| title | An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications |
| topic | Computational Geometry 68Q01, 68W01, 14Q20 F.2.2; I.3.5 |
| url | https://arxiv.org/abs/1812.10269 |