Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
type: Item
instance of: scholarly article
title: Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
zbMATH Open document ID: 1422.68106
author: Timothy M. Chan
published in: Discrete \& Computational Geometry
publication date: 2019-05-21T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7226/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 7057365
zbMATH Keywords: geometric data structures
zbMATH Keywords: range searching
zbMATH Keywords: nearest neighbor searching
zbMATH Keywords: k-d trees
zbMATH Keywords: range trees
zbMATH Keywords: all-pairs shortest paths
zbMATH Keywords: Boolean matrix multiplication
MaRDI profile type: Publication
OpenAlex ID: W2920487484
cites work: More Applications of the Polynomial Method to Algorithm Design
cites work: Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
cites work: Improved parallel integer sorting without concurrent writing
cites work: Q5616735
cites work: Geometric applications of a randomized optimization technique
cites work: All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
cites work: More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
cites work: Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
cites work: Orthogonal range searching on the RAM, revisited
cites work: Q5417615
cites work: Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
cites work: Asymptotically optimal covering designs
cites work: An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
cites work: Approximate nearest neighbor: towards removing the curse of dimensionality
cites work: On approximate nearest neighbors under \(l_\infty\) norm
cites work: Faster Online Matrix-Vector Multiplication
cites work: Powers of tensors and fast matrix multiplication
cites work: Q4607951
cites work: Computing dominances in \(E^ n\)
cites work: Q3694703
cites work: Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Q2934692
cites work: Multiplying matrices faster than coppersmith-winograd
cites work: Faster all-pairs shortest paths via circuit complexity
cites work: An improved combinatorial algorithm for Boolean matrix multiplication
Wikidata QID: Q128283852
DOI: 10.1007/S00454-019-00062-5
description: scientific article