Fast local searches and updates in bounded universes

DOI10.1016/j.comgeo.2012.01.002zbMath1253.68111MaRDI QIDQ691776

Karim Douïeb, John Howat, Vida Dujmović, Pat Morin, Prosenjit Bose

Publication date: 4 December 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.002

zbMATH Keywords

range search; bounded universe; distance sensitivity; nearest neighbour search; predecessor search

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

Related Items

Cross-document pattern matching, Biased predecessor search

Cites Work

• Unnamed Item
• Unnamed Item
• Preserving order in a forest in less than logarithmic time and linear space
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal bounds for the predecessor problem and related problems
• Data Structures with Local Update Operations
• Dynamic ordered sets with exponential search trees
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Priority Search Trees
• Efficient data structures for range searching on a grid
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Orthogonal range searching on the RAM, revisited
• Algorithms - ESA 2003
• Optimal finger search trees in the pointer machine
• Efficient regular data structures and algorithms for dilation, location, and proximity problems