We present an optimal data structure for storing a sequence of similar lists; it supports rapid searching of an arbitrary list. Applications include an optimal planar point location algorithm, more general than previous ones, a 3-dimensional point location algorithm, and a new representation scheme for polyhedra.
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics