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/12:10125730!RIV13-MSM-11320___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1M0545)
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Matoušek, Jiří
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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	156311
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/12:10125730
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...ontrolniKodProRIV	[6F68B2A30956]
http://linked.open...v/mistoKonaniAkce	New Brunswick, New Jersey
http://linked.open...i/riv/mistoVydani	Los Alamitos
http://linked.open...i/riv/nazevZdroje	2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
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...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2012
http://linked.open...iv/tvurceVysledku	Matoušek, Jiří Agarwal, Pankaj Sharir, Micha
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2012-10-20 (xsd:date)
issn	0272-5428
number of pages	10 (xsd:int)
http://bibframe.org/vocab/doi	10.1109/FOCS.2012.32
http://purl.org/ne...btex#hasPublisher	Institute of Electrical and Electronics Engineers, Inc.
https://schema.org/isbn	978-1-4673-4383-1
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