Optimal static range reporting in one dimension

DOI10.1145/380752.380842zbMath1323.68536MaRDI QIDQ5176005

Theis Rauhe, Stephen Alstrup, Gerth Brodal

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380842

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Unnamed Item, Unnamed Item, Finding top-\(k\) longest palindromes in substrings, Document retrieval with one wildcard, Reporting consecutive substring occurrences under bounded gap constraints, Substring range reporting, Orthogonal range searching in linear and almost-linear space, Ranked document retrieval for multiple patterns, Optimal bounds for the predecessor problem and related problems, Succinct non-overlapping indexing, On hardness of several string indexing problems, Succinct indices for path minimum, with applications, Ranked Document Retrieval with Forbidden Pattern, Succinct Non-overlapping Indexing, Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints, Substring Range Reporting, Fault-Tolerant Compact Routing Schemes for General Graphs

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)