Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

DOI10.4230/LIPICS.SOCG.2017.27zbMATH Open1433.68484OpenAlexW2724706363MaRDI QIDQ4580101FDOQ4580101

Authors Timothy M. Chan 

Publication date 13 August 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2017.27

zbMATH Keywords

computational geometrydata structuresrange searchingnearest neighbor searching

Mathematics Subject Classification ID

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

Recommendations

• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching
• Compact and succinct data structures for multidimensional orthogonal range searching
• Orthogonal range searching in linear and almost-linear space
• Orthogonal Range Searching in Linear and Almost-Linear Space
• On the average performance of orthogonal range search in multidimensional data structures
• scientific article; zbMATH DE number 2086648
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Efficient top-\(k\) queries for orthogonal ranges
• Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions

Cited In (5)

• The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
• On k-d Range Search with Patricia Tries
• Title not available (Why is no real title available?)

This page was built for publication: Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

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