A Functional Approach to Data Structures and Its Use in Multidimensional Searching
SIAM Journal on Computing1988Vol. 17(3), pp. 427–462
Citations Over TimeTop 10% of 1988 papers
Abstract
We establish new upper bounds on the complexity of multidimensional searching. Our results include, in particular, linear-size data structures for range and rectangle counting in two dimensions with logarithmic query time. More generally, we give improved data structures for rectangle problems in any dimension, in a static as well as a dynamic setting. Several of the algorithms we give are simple to implement and might be the solutions of choice in practice. Central to this paper is the nonstandard approach followed to achieve these results. At its root we find a redefinition of data structures in terms of functional specifications.
Related Papers
- → Determining camera parameters from the perspective projection of a rectangle(1989)104 cited
- → Cutting squares from rectangles(1974)7 cited
- → Conformal mapping of a symmetrically horizontal slit rectangle onto a rectangle with a square removed(2009)
- From rectangle-shaped to square-shaped antennas based on graphene: T-shaped, Cross-shaped and Rectangle-shaped Structure Transitions(2014)
- → Exact and beam solutions for a narrow clamped rectangle(2022)