Efficient Dynamic Data Structures for Geometric Problems

This project will investigate the design of efficient dynamic data structures for geometric problems. Three classes of problems will be considered: point location in a dynamic planar subdivision, dynamic intersection searching for a generalized class of intersection problems, and maintenance of functions defined on dynamic sets of geometric objects. These problems arise in diverse applications such as, for instance, facilities location, VLSI, and clustering. Both theoretical issues (i.e., design of asymptotically-efficient schemes) and practical issues (i.e., design, implementation, and evaluation of simple schemes) will be addressed. The methods to be employed include a combination of advanced data structuring techniques, geometric properties, and approximation. It is anticipated that this research will yield improved dynamic solutions for a variety of point location problems as well as efficient dynamic solutions for the other two classes of problems which have for the most part eluded efficient dynamization.