TY - GEN
T1 - SLIMMING DOWN SEARCH STRUCTURES
T2 - A FUNCTIONAL APPROACH TO ALGORITHM DESIGN.
AU - Chazelle, Bernard
PY - 1985
Y1 - 1985
N2 - New upper bounds on the complexity of several 'rectangle' problems are established. The results include, for instance, optimal algorithms for range counting and rectangle searching in two dimensions. These involve linear space implementations of range trees and segment trees. Thee algorithms are simple and practical; they can be dynamized and taken into higher dimensions. Also of interest is the nonstandard approach used to obtain these results: it involves transforming data structures on the basis of functional specifications.
AB - New upper bounds on the complexity of several 'rectangle' problems are established. The results include, for instance, optimal algorithms for range counting and rectangle searching in two dimensions. These involve linear space implementations of range trees and segment trees. Thee algorithms are simple and practical; they can be dynamized and taken into higher dimensions. Also of interest is the nonstandard approach used to obtain these results: it involves transforming data structures on the basis of functional specifications.
UR - http://www.scopus.com/inward/record.url?scp=0022214124&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022214124&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1985.51
DO - 10.1109/sfcs.1985.51
M3 - Conference contribution
AN - SCOPUS:0022214124
SN - 0818606444
SN - 9780818606441
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 165
EP - 174
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -