Optimal static range reporting in one dimension

DOI10.1145/380752.380842zbMath1323.68536OpenAlexW2112821228MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (17)

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

Cites Work

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

This page was built for publication: Optimal static range reporting in one dimension