This project investigates the construction and maintenance of geometric structures, as well as methods for efficiently searching in such structures. This involves studying known computational geometry problems which are as yet unsolved, new computational geometry problems dealing with the dynamic maintenance of geometric structures, and new computational geometry problems arising from applications in computer graphics and computer vision. The algorithms developed are for sequential and parallel models of computation.