THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE

DOI10.1142/S0218195991000049zbMath0724.68047MaRDI QIDQ3212290

Burton Rosenberg, Bernard Chazelle

Publication date: 1991

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

partial sumsorthogonal range searchinglower-bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

Succinct indices for path minimum, with applications ⋮ Can visibility graphs be represented compactly? ⋮ Range Minimum Query Indexes in Higher Dimensions ⋮ The optimal all-partial-sums algorithm in commutative semigroups and its applications for image thresholding segmentation ⋮ Multidimensional segment trees can do range updates in poly-logarithmic time ⋮ Path Minima in Incremental Unrooted Trees ⋮ How hard is half-space range searching? ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ High girth augmented trees are huge ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Orthogonal Range Searching for Text Indexing ⋮ Array Range Queries

This page was built for publication: THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE