About: On range searching with semialgebraic sets II

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On range searching with semialgebraic sets II Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://arxiv.org/abs/1208.3384
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 similar structures for simplex range searching, and, for $d\ge 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^d\setminus 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. 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 similar structures for simplex range searching, and, for $d\ge 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^d\setminus 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. (en)
Title	On range searching with semialgebraic sets II On range searching with semialgebraic sets II (en)
skos:prefLabel	On range searching with semialgebraic sets II On range searching with semialgebraic sets II (en)
skos:notation	RIV/00216208:11320/13:10173445!RIV14-MSM-11320___
http://linked.open...avai/riv/aktivita	I
http://linked.open...avai/riv/aktivity	I
http://linked.open...iv/cisloPeriodika	6
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Matoušek, Jiří
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	93784
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/13:10173445
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	range searching; data structure; semialgebraic set (en)
http://linked.open.../riv/klicoveSlovo	data structure range searching semialgebraic set
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[8F6A6976D7D9]
http://linked.open...i/riv/nazevZdroje	SIAM Journal on Computing
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	42
http://linked.open...iv/tvurceVysledku	Matoušek, Jiří Agarwal, Pankaj Sharir, Micha
http://linked.open...ain/vavai/riv/wos	000328889400001
issn	0097-5397
number of pages	34 (xsd:int)
http://bibframe.org/vocab/doi	10.1137/120890855
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software