REU Student	Faculty Advisor
Noah Falk	Guy Blelloch

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.

Preliminary Presentation: pdf, ppt

 

Other Mini-PROBEs for Summer 2003

Algorithms for Facility Location
Anonymous Communication
Designing Overlay Multicast Networks for Streaming
Moving Mesh Simulations
Dynamic Algorithms
HumanAUT