Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
DOI10.1007/s00454-019-00062-5zbMath1422.68106OpenAlexW2920487484WikidataQ128283852 ScholiaQ128283852MaRDI QIDQ2415385
Publication date: 21 May 2019
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7226/
range searchinggeometric data structuresBoolean matrix multiplicationrange treesnearest neighbor searchingk-d treesall-pairs shortest paths
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing dominances in \(E^ n\)
- Improved parallel integer sorting without concurrent writing
- On approximate nearest neighbors under \(l_\infty\) norm
- An improved combinatorial algorithm for Boolean matrix multiplication
- Geometric applications of a randomized optimization technique
- Asymptotically optimal covering designs
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Powers of tensors and fast matrix multiplication
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Faster Online Matrix-Vector Multiplication
- Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
- Faster all-pairs shortest paths via circuit complexity
- More Applications of the Polynomial Method to Algorithm Design
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Orthogonal range searching on the RAM, revisited
- Multiplying matrices faster than coppersmith-winograd
This page was built for publication: Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
