On range searching with semialgebraic sets II

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On range searching with semialgebraic sets II

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On range searching with semialgebraic sets II

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

ISBN

978-1-4673-4383-1

ISSN

0272-5428

e-ISSN

—

Počet stran výsledku

10

Strana od-do

420-429

Název nakladatele

Institute of Electrical and Electronics Engineers, Inc.

Místo vydání

Los Alamitos

Místo konání akce

New Brunswick, New Jersey

Datum konání akce

20. 10. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—