Approximate range searching

DOI10.1016/S0925-7721(00)00022-5zbMath0968.68167MaRDI QIDQ1595401

David M. Mount, Sunil Arya

Publication date: 13 September 2001

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

range searching problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (27)

Topology B-trees and their applications ⋮ POINT SET DISTANCE AND ORTHOGONAL RANGE PROBLEMS WITH DEPENDENT GEOMETRIC UNCERTAINTIES ⋮ Range searching in multidimensional databases using navigation metadata ⋮ Half-plane point retrieval queries with independent and dependent geometric uncertainties ⋮ Approximate range searching in external memory ⋮ Approximate Polytope Membership Queries ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Robust proximity search for balls using sublinear space ⋮ SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS ⋮ Energy-efficient paths in radio networks ⋮ Approximate range closest-pair queries ⋮ Constructing minimum-interference networks ⋮ I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ⋮ Approximate Range Searching in External Memory ⋮ GEOMETRIC ALGORITHMS FOR DENSITY-BASED DATA CLUSTERING ⋮ Approximate range searching in higher dimension ⋮ Reporting flock patterns ⋮ On approximate range counting and depth ⋮ Approximate range searching using binary space partitions ⋮ Approximate range searching: The absolute model ⋮ Go with the flow, on Jupiter and snow. Coherence from model-free video data without trajectories ⋮ The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching ⋮ Efficient \(c\)-oriented range searching with DOP-trees ⋮ Unnamed Item ⋮ The effect of corners on the complexity of approximate range searching ⋮ Kernel-independent adaptive construction of \(\mathcal{H}^2\)-matrix approximations ⋮ Unnamed Item

Cites Work

• Unnamed Item
• How hard is half-space range searching?
• Range searching with efficient hierarchical cuttings
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Approximate closest-point queries in high dimensions
• Point location in fat subdivisions
• Quasi-optimal range searching in spaces of finite VC-dimension
• Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Lower Bounds on the Complexity of Polytope Range Searching
• Rate-distortion performance of DPCM schemes for autoregressive sources
• Polygon Retrieval
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields

This page was built for publication: Approximate range searching