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.
This material is based upon work supported by National Science
Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed
in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation