Dynamic 3-sided planar range queries with expected doubly logarithmic time

DOI10.1007/978-3-642-10631-6_21MaRDI QIDQ3652205zbMATH OpenOpenAlexFDO

Authors Gerth Stølting Brodal, A. C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Tsichlas

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.2702

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Data structures (68P05)

Abstract: This work studies the problem of 2-dimensional searching for the 3-sided range query of the form $[a,b]imes(-infty,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.

Recommendations

• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• Dynamic planar range skyline queries in log logarithmic expected time
• Dynamic Planar Range Maxima Queries
• Towards an optimal method for dynamic planar point location
• Dynamic range selection in linear space

Cited in

(6)

• Dynamic planar range skyline queries in log logarithmic expected time
• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• Dynamic Planar Range Maxima Queries
• Dynamic range selection in linear space
• scientific article; zbMATH DE number 1953879 (Why is no real title available?)
• I/O-efficient data structures for colored range and prefix reporting

This page was built for publication: Dynamic 3-sided planar range queries with expected doubly logarithmic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652205)