Slimming Down Search Structures: A Functional Approach to Algorithm Design

We establish new upper bounds on the complexity of several "rectangle" problems. Our 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. The algorithms we give are simple and practical; they can be dynamized and taken into higher dimensions. Also of interest is the nonstandard approach which we follow to obtain these results: it involves transforming data structures on the basis of functional specifications.

Authors

• Bernard Chazelle

Keywords

• Algorithm design and analysis
• Data structures
• Computer science
• Upper bound
• Buildings
• Process design
• Shape
• Data Structure
• Tree Nodes
• Tree Search
• Binary Tree
• Tree Segmentation
• Design Point Of View
• Pair Formation
• Least Significant Bit
• Binary Search
• Complete Tree
• Query Time
• Balanced Tree
• Left Child
• Range Query