Quasi-optimal range searching in spaces of finite VC-dimension
type: Item
instance of: scholarly article
title: Quasi-optimal range searching in spaces of finite VC-dimension
zbMATH Open document ID: 0681.68081
DOI: 10.1007/BF02187743
author: Bernard Chazelle
author: Emo Welzl
published in: Discrete \& Computational Geometry
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131092
review text: The paper deals with the range searching problem, i.e. given a finite set S of points in d-dimensional space \(E^ d\) and a query region \(q\subseteq E^ d\), report or count the points of \(S\cap q\). On more abstract level one can consider a range space (X,R), where X is an arbitrary set (the elements of X are called points) and R is a subset of its power set (the members of R are called ranges). The authors consider the use of partition trees to solve this problem and show that ``good'' partition trees (i.e. with sublinear query time and linear size) can be characterized as those defined by range spaces of finite Vapnik- Chervonenkis dimension. Then they show that simplex and spherical range searching problems are both solvable in \(\theta (n^{1-1/d}\alpha (n))\) query time and \(\theta\) (n) storage in the arithmetical model, where \(\alpha\) (n) denotes the inverse Ackerman function. Finally algorithms for polygon, disk and tetrahedron range searching on RAM or pointer machine are discussed.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4115986
zbMATH Keywords: range searching
zbMATH Keywords: range spaces
zbMATH Keywords: Vapnik-Chervonenkis dimension
Wikidata QID: Q54309753
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
cites work: Density and dimension
cites work: Visibility and intersection problems in plane geometry
cites work: Fast detection of polyhedral intersection
cites work: Central limit theorems for empirical measures
cites work: Q3772828
cites work: Implicitly representing arrangements of lines or segments
cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time
cites work: Lower Bounds on the Complexity of Some Optimal Data Structures
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Q3219753
cites work: Combinatorial solutions of multidimensional divide-and-conquer recurrences
cites work: Q3992847
cites work: On the density of families of sets
cites work: Efficiency of a Good But Not Linear Set Union Algorithm
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Polygon Retrieval
cites work: On the Complexity of Maintaining Partial Sums
OpenAlex ID: W2025809050
DBLP publication ID: journals/dcg/ChazelleW89
Recommended article: Tight lower bounds for halfspace range searching
Recommended article: Quasi-optimal upper bounds for simplex range searching and new zone theorems
Recommended article: Orthogonal range searching in linear and almost-linear space
Recommended article: Orthogonal Range Searching in Linear and Almost-Linear Space
Recommended article: Approximate range searching in higher dimension
Recommended article: Lower Bounds on the Complexity of Polytope Range Searching
Recommended article: Approximate range searching using binary space partitions
Recommended article: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Recommended article: Near-optimal search time in \(\delta \)-optimal space
description: scientific article; zbMATH DE number 4115986