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

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

zbMATH Keywords

computational geometrydata structuresrange searchingnearest neighbor searching

Mathematics Subject Classification ID

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

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 that?)

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)