Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time

2012/01/12 by Brodal, Gerth Stølting, Kaporis, Alexis C., Papadopoulos, Apostolos N. +3
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1201.2702

Abstract

This work studies the problem of 2-dimensional searching for the 3-sided range query of the form [a, b]× (-∞, c] in both main and external memory, by considering a variety of input distributions. We present three sets of solutions each of which examines the 3-sided problem in both RAM and I/O model respectively. The presented data structures are deterministic and the expectation is with respect to the input distribution.

Related

• Dynamic Range Reporting in External Memory
• External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates
• Incremental Planar Nearest Neighbor Queries with Optimal Query Time
• New Data Structures for Orthogonal Range Reporting and Range Minima Queries
• Dynamic Planar Point Location in External Memory