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

DOI10.1016/J.TCS.2014.01.014zbMATH Open1282.68096OpenAlexW2133951680MaRDI QIDQ2437762FDOQ2437762

Authors: Gerth Stølting Brodal, Konstantinos Tsakalidis, A. C. Kaporis, A. N. Papadopoulos, Spyros Sioutas, 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

Recommendations

• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• Dynamic planar range skyline queries in log logarithmic expected time
• Priority Search Trees
• Dynamic orthogonal range searching on the RAM, revisited
• Amortized bounds for dynamic orthogonal range reporting

zbMATH Keywords

computational geometrydynamic data structuresaverage case analysis3-sided range reportingdoubly logarithmic

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• Dynamic Planar Range Maxima Queries
• Title not available (Why is that?)
• Dynamic planar range skyline queries in log logarithmic expected time

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 Q2437762)