Abstract
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.
| Original language | English (US) |
|---|---|
| Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |
| Publisher | IEEE |
| Pages | 165-174 |
| Number of pages | 10 |
| ISBN (Print) | 0818606444 |
| State | Published - Dec 1 1985 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture