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

DOI10.1016/j.tcs.2014.01.014zbMath1282.68096OpenAlexW2133951680MaRDI QIDQ2437762

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

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.014

zbMATH Keywords

computational geometryaverage case analysisdynamic data structures3-sided range reportingdoubly logarithmic

Mathematics Subject Classification ID

Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Dynamic planar range skyline queries in log logarithmic expected time, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• A log log n data structure for three-sided range queries
• A balanced search tree O(1) worst-case update time
• Indexing for data models with constraints and classes
• Dynamic interpolation search
• Fast Algorithms for Finding Nearest Common Ancestors
• Dynamic ordered sets with exponential search trees
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Dynamic Interpolation Search Revisited
• Priority Search Trees
• Efficient data structures for range searching on a grid
• Deletions That Preserve Randomness
• Algorithms on Strings, Trees and Sequences
• Dynamic interpolation search in o(log log n) time
• Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
• Algorithms - ESA 2003
• Algorithms and Computation