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年中在这些问题上取得的重大进展开辟了许多新的具有挑战性的研究方向，包括：在更高维度的表面安排中与子结构（下包络，单细胞，区域，水平，垂直分解）相关的组合和算法问题。 真实的代数几何中计算真实的半代数集的连通分支、分层、维数等拓扑参数的相关算法。 涉及线段或曲线的平面排列的图形绘制和其他算法、组合和拓扑问题。 这些结果的应用到许多领域，包括机器人的运动规划，计算机图形学中的渲染和建模问题，广义Voronoi图和几何优化问题，包括计量和设施位置的问题。 这项研究的一个重要特点是在计算和组合几何的基础研究和各种应用领域之间的交叉施肥。 另一个主题是安排的组合分析和设计有效的算法来构建和利用这些结构之间的紧密联系。算法的效率通常取决于要计算的结构的大小，并且大部分工作都致力于限制这个数量。