On range searching with semialgebraic sets II
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125730" target="_blank" >RIV/00216208:11320/12:10125730 - isvavai.cz</a>
Result on the web
<a href="http://arxiv.org/abs/1208.3384" target="_blank" >http://arxiv.org/abs/1208.3384</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/FOCS.2012.32" target="_blank" >10.1109/FOCS.2012.32</a>
Alternative languages
Result language
angličtina
Original language name
On range searching with semialgebraic sets II
Original language description
Let $P$ be a set of $n$ points in $R^d$. We present a linear-size data structure for answering range queries on $P$ with constant-complexity semialgebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similarstructures for simplex range searching, and, for $dge 5$, significantly improves earlier solutions by the first two authors obtained in~1994. This almost settles a long-standing open problem in range searching. The data structure is based on the polynomial-partitioning technique of Guth and Katz, which shows that for a parameter $r$, $1 < r le n$, there exists a $d$-variate polynomial $f$ of degree $O(r^{1/d})$ such that each connected component of $R^dsetminus Z(f)$ contains at most $n/r$ points of $P$, where $Z(f)$ is the zero set of $f$. We present an efficient randomized algorithm for computing such a polynomial partition, which is of independent interest and is likely to have additional applications.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
ISBN
978-1-4673-4383-1
ISSN
0272-5428
e-ISSN
—
Number of pages
10
Pages from-to
420-429
Publisher name
Institute of Electrical and Electronics Engineers, Inc.
Place of publication
Los Alamitos
Event location
New Brunswick, New Jersey
Event date
Oct 20, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—