This project investigates basic research in computational geometry that is well-motivated by applications in geometric computing. Specific focus is given to the construction and maintenance of geometric structures, as well as methods for efficiently searching in such structures, with principle motivating applications coming from computational metrology, computational graph drawing, and geometric information retrieval. Emphasis is placed upon the design of algorithms for single processors as well as methods for exploiting coarse-grain parallelism such as exists in systems with parallel disk arrays or clusters of workstations. ***
