The effect of corners on the complexity of approximate range searching
From MaRDI portal
Publication:1014333
DOI10.1007/s00454-009-9140-zzbMath1165.68060OpenAlexW1967952322MaRDI QIDQ1014333
Sunil Arya, David M. Mount, Theocharis Malamatos
Publication date: 27 April 2009
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-009-9140-z
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items
On the combinatorial complexity of approximating polytopes ⋮ Tight lower bounds for halfspace range searching ⋮ Approximate range searching: The absolute model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- How hard is half-space range searching?
- Range searching with efficient hierarchical cuttings
- Intrinsic volumes and f-vectors of random polytopes
- Geometric algorithms and combinatorial optimization
- Approximate range searching
- Approximate range searching in higher dimension
- On the importance of idempotence
- Lower Bounds on the Complexity of Polytope Range Searching
- Space-efficient approximate Voronoi diagrams
- Approximate Range Searching: The Absolute Model
- On the Complexity of Maintaining Partial Sums
- Convex bodies, economic cap coverings, random polytopes
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Space-Time Tradeoffs for Emptiness Queries
- The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
This page was built for publication: The effect of corners on the complexity of approximate range searching
