How hard is half-space range searching?
type: Item
instance of: scholarly article
title: How hard is half-space range searching?
zbMATH Open document ID: 0778.68087
DOI: 10.1007/BF02573971
author: Hervé Brönnimann
author: János Pach
author: Bernard Chazelle
published in: Discrete \& Computational Geometry
publication date: 1993-09-30T00:00:00Z
full work available at URL: https://eudml.org/doc/131267
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 417111
zbMATH Keywords: range searching
zbMATH Keywords: lower bounds
Wikidata QID: Q29394177
MaRDI profile type: Publication
cites work: Applications of a new space-partitioning technique
cites work: Convex bodies, economic cap coverings, random polytopes
cites work: Inherent complexity trade-offs for range query problems
cites work: Lower Bounds on the Complexity of Polytope Range Searching
cites work: Lower bounds for orthogonal range searching: I. The reporting case
cites work: Lower bounds for orthogonal range searching: part II. The arithmetic model
cites work: THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
cites work: Lower bounds on the complexity of simplex range reporting on a pointer machine
cites work: Quasi-optimal upper bounds for simplex range searching and new zone theorems
cites work: Quasi-optimal range searching in spaces of finite VC-dimension
cites work: Applications of random sampling in computational geometry. II
cites work: Geometric retrieval problems
cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time
cites work: The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
cites work: A Lower Bound on the Complexity of Orthogonal Range Queries
cites work: Lower Bounds on the Complexity of Some Optimal Data Structures
cites work: On the mean value of the volume of a random polytope in a convex set
cites work: Geometric algorithms and combinatorial optimization
cites work: \(\epsilon\)-nets and simplex range queries
cites work: A theorem on non-homogeneous lattices
cites work: Q3219753
cites work: Q4110292
cites work: Q3481743
cites work: Polygon Retrieval
cites work: On the Complexity of Maintaining Partial Sums
OpenAlex ID: W1995232397
DBLP publication ID: journals/dcg/BronnimannCP93
description: scientific article; zbMATH DE number 417111