Biased range trees

DOI10.1007/s00453-010-9440-yzbMath1241.68054MaRDI QIDQ2428657

Pat Morin, John Howat, Vida Dujmović

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9440-y

zbMATH Keywords

data structures; computational geometry; orthogonal range searching; distribution-sensitive data structures

Mathematics Subject Classification ID

05C05: Trees

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Biased range trees, A History of Distribution-Sensitive Data Structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Multidimensional divide-and-conquer
• Fractional cascading. I: A data structuring technique
• Nearly optimal binary search trees
• Expected asymptotically optimal planar point location
• Biased range trees
• Ignoring ignorance and agreeing to disagree
• Entropy, triangulation, and point location in planar subdivisions
• On the Complexity of Maintaining Partial Sums
• Filtering Search: A New Approach to Query-Answering
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Multidimensional binary search trees used for associative searching
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Optimal Expected-Case Planar Point Location
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting