Studies of Geometric Arrangements and their Algorithmic Applications

几何排列及其算法应用研究

• 批准号: 0098246
• 负责人: Richard Pollack
• 金额: $ 59.8万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098246&HistoricalAwards=false
• 关键词: Studies; Geometric; Arrangements; their; Algorithmic

Computational geometry covers a wide range of applications, such as motion planning and computer graphics, and its contribution to their solution involves the use of sophisticated techniques drawn from many branches of mathematics and computer science. The investigators extensively study many basic and applied problems in the area, including motion planning, Voronoi diagrams, combinatorial and algebraic analysis of arrangements of curves and algebraic surfaces, graph drawing, randomized algorithms, and geometric optimization.A major portion of this research involves the study of arrangements of curves and surfaces. The significant progress made by the PI's on these problems during the past 15 years has opened up many new challenging research directions, including:Combinatorial and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions) in arrangements of surfaces in higher dimensions. Related algorithms in real algebraic geometry for computing connected components, stratifications, the dimension and othertopological parameters of real semi-algebraic sets. Graph drawing and other algorithmic, combinatorial, and topological problems involving planar arrangements of segments or curves. Applications of these results to numerous areas, including motion planning in robotics, rendering and modeling problems in computer graphics, generalized Voronoi diagrams and geometric optimization problems, including problems in metrology and facility location. An important feature of this research is the cross-fertilization between basic research in computational and combinatorial geometry and various application areas. Another theme is the strong connection between the combinatorial analysis of arrangements and the design of efficient algorithms for constructing and utilizing these structures. The efficiency of the algorithms often crucially depends on the size of the structure to be computed, and most of the work is devoted to bounding this quantity.

计算几何涵盖了广泛的应用，例如运动规划和计算机图形学，其对解决方案的贡献涉及使用来自数学和计算机科学许多分支的复杂技术。研究人员广泛研究该领域的许多基础和应用问题，包括运动规划、Voronoi 图、曲线和代数曲面排列的组合和代数分析、图形绘制、随机算法和几何优化。这项研究的主要部分涉及研究曲线和曲面的排列。 PI 在过去 15 年中在这些问题上取得的重大进展开辟了许多新的具有挑战性的研究方向，包括：与子结构（下封套、单单元、区域、水平、垂直分解）相关的组合和算法问题更高维度的表面。 实代数几何中用于计算实半代数集的连通分量、分层、维数和其他拓扑参数的相关算法。 图形绘制以及涉及线段或曲线的平面排列的其他算法、组合和拓扑问题。 这些结果可应用于众多领域，包括机器人运动规划、计算机图形学中的渲染和建模问题、广义维诺图和几何优化问题，包括计量和设施选址问题。 这项研究的一个重要特点是计算几何和组合几何的基础研究与各种应用领域之间的交叉融合。 另一个主题是排列的组合分析与构建和利用这些结构的有效算法的设计之间的紧密联系。算法的效率通常很大程度上取决于要计算的结构的大小，并且大部分工作都致力于限制这个数量。