Efficient Dynamic Data Structures for Geometric Problems

几何问题的高效动态数据结构

• 批准号: 9200270
• 负责人: Ravi Janardan
• 金额: $ 11.21万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-07-01 至 1994-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9200270&HistoricalAwards=false
• 关键词: Efficient; Dynamic; Data; Structures; Geometric

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.

这个项目将研究设计有效的动态数据 几何问题的结构。 三种类型的问题将是 考虑：点位置在一个动态的平面细分，动态 广义交类的交搜索 问题，并维护在动态集合上定义的函数， 几何物体 这些问题出现在不同的应用中， 例如，设施位置、超大规模集成电路和集群。 两 理论问题（即，渐近有效方案的设计） 和实际问题（即，设计、实施和评估 简单的方法）。 拟采用的方法 包括高级数据结构化技术组合， 几何性质和近似。 预计这一 研究将为各种点产生改进的动态解决方案 定位问题以及其他有效的动态解决方案 这两类问题在很大程度上回避了有效的 动态化