Efficient Dynamic Data Structures for Geometric Problems

这个项目将研究几何问题的有效动态数据结构的设计。三种类型的问题将被考虑：在一个动态平面细分点的位置，动态交集搜索一个广义类的交集问题，和维持在几何对象的动态集合上定义的函数。这些问题出现在不同的应用程序中，例如，设施位置、VLSI和集群。理论问题（即，渐近有效方案的设计）和实际问题（即，简单方案的设计，实施和评估）将被解决。所采用的方法包括高级数据结构技术、几何属性和近似的组合。预计本研究将为各种点定位问题提供改进的动态解，并为其他两类问题提供有效的动态解，这两类问题在很大程度上避免了有效的动态化。

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.