On k-d Range Search with Patricia Tries

DOI10.1137/060653780zbMATH Open1225.68083OpenAlexW2070759438MaRDI QIDQ3532568

Bradford G. Nickerson, Qingxiu Shi

Publication date: 28 October 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060653780

zbMATH Keywords

Patricia trieapproximate range searchorthogonal range search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Data structures (68P05) Approximation algorithms (68W25)

Recommendations

• Halfspace range search: An algorithmic application of k-sets 👍 👎
• \(d\)-dimensional range search on multicomputers 👍 👎
• Quasi-optimal range searching in spaces of finite VC-dimension 👍 👎
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back 👍 👎
• ON MULTI-LEVEL k-RANGES FOR RANGE SEARCH 👍 👎
• Lower Bounds on the Complexity of Polytope Range Searching 👍 👎
• Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back 👍 👎
• On the difficulty of range searching 👍 👎
• Analysis of range search for random \(k-d\) trees 👍 👎

This page was built for publication: On k-d Range Search with Patricia Tries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532568)