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

Gerth Stølting Brodal, Alexis Kaporis, Apostolos Papadopoulos, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas

In Theoretical Computer Science, volume 526, pages 58-74, 2014.

Abstract

The Priority Search Tree is the classic solution for the problem of dynamic 2-dimensional searching for the orthogonal query range of the form [a, b]x (-∞, c] (3-sided rectangle). It supports all operations in logarithmic worst case complexity in both main and external memory. In this work we show that the update and query complexities can we improved to expected doubly-logarithmic, when the input coordinates are being continuously drawn from specific probability distributions. We present three pairs of linear space solutions for the problem, i.e. a RAM and a corresponding I/O model variant:

(1) First, we improve the update complexity to doubly-logarithmic expected with high probability, under the most general assumption that both the x- and y-coordinates of the input points are continuously being drawn from a distribution whose density function is unknown but fixed.

(2) Next, we improve both the query complexity to doubly-logarithmic expected with high probability and the update complexity to doubly-logarithmic amortized expected, by assuming that only the x-coordinates are being drawn from a class of smooth distributions, and that the deleted points are selected uniformly at random among the currently stored points. In fact, the y-coordinates are allowed to be arbitrarily distributed.

(3) Finally, we improve both the query and the update complexity to doubly-logarithmic expected with high probability by moreover assuming the y-coordinates to be continuously drawn from a more restricted class of realistic distributions.

All data structures are deterministic and their complexity's expectation is with respect to the assumed distributions. They comprise combinations of known data structures and of two new data structures introduced here, namely the Weight Balanced Exponential Tree and the External Modified Priority Search Tree.

Copyright notice

Copyright © 2014 by Elsevier Inc.. All rights reserved.

Online version

tcs14.pdf (486 Kb)

DOI

10.1016/j.tcs.2014.01.014

BIBTEX entry

@article{tcs14,
  author = "Gerth St{\o}lting Brodal and Alexis Kaporis and Apostolos Papadopoulos and Spyros Sioutas and Konstantinos Tsakalidis and Kostas Tsichlas",
  doi = "10.1016/j.tcs.2014.01.014",
  issn = "0304-3975",
  journal = "Theoretical Computer Science",
  pages = "58-74",
  publisher = "Elsevier Science",
  title = "Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time",
  volume = "526",
  year = "2014"
}

Other versions