The effect of corners on the complexity of approximate range searching

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

zbMATH Keywords

computational complexityapproximation algorithmsrange searchingidempotence

Mathematics Subject Classification ID

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 (3)

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