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

DOI10.1016/J.TCS.2014.01.014MaRDI QIDQ2437762zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(4)

• I/O-efficient data structures for colored range and prefix reporting
• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• Dynamic Planar Range Maxima Queries
• 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)