Point location is a critical component in many
applications of computational geometry. For planar subdivisions
several algorithms have been developed that can locate points
in O(log n) time (n is the size of the description of the subdivision).
These methods in practice, however, can require significantly
more memory than the description of the subdivision itself and
can be impractical for very large meshes. We are studying methods
that can reduce the number of bits needed to store point-location
data-structures to O(n) bits. This an O(log n) improvement over
the current best theoretical results and we believe can lead to
compact representations in practice. We are initially limiting
ourselves to considering triangular subdivisions.
Other Mini-PROBEs for Summer 2003