Geometric Arrangements and their Algorithmic Applications

几何排列及其算法应用

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

Computational geometry is a major research area in computer science, which aims to design efficient algorithms for problems of geometric nature, which arise in many applications. In this research, the investigators continue their long-term study of basic and applied problems in computational geometry, including motion planning problems in robotics, visibility problems in computer graphics, efficient algorithms for linear programming and other geometric optimization problems. These studies cultivate and expose the rich cross-fertilization between basic research in computational and combinatorial geometry and the various application areas, where problems in one area motivate the study of new basic problems whose solution in turn finds applications in many others. There is a strong connection between the combinatorial, algebraic, and topological analysis of arrangements of geometric objects and the design of corresponding efficient algorithms: often the algorithmic complexity (efficiency) of such an algorithm crucially depends on the size or the degree of freedom (combinatorial or algebraic complexity, resp.) of the arrangement.A major portion of this research is devoted to the study of arrangements of curves and surfaces. Specifically, it studies(1) Combinatorial, topological and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions, etc.) in arrangements of surfaces in higher dimensions;(2) Related algorithms in real algebraic geometry for computing connected components, stratifications and the dimension of real semi-algebraic sets.(3) Applications of these results to motion planning in robotics, to various visibility and intersection problems in computer graphics, to generalized Voronoi diagrams in higher dimensions, and to many geometric problems at large; and(4) Combinatorial, topological, and algorithmic problems involving planar arrangements of segments or curves, including graph drawings.This research is expected to have an impact on the interaction between mathematics and computer science in geometry, via the dissemination of its results in major conferences and workshops, the journals that they have been editing, the monographs and surveys that the investigators have been writing, and the numerous graduate students that they have been supervising.

计算几何是计算机科学中的一个重要研究领域，其目的是为几何性质的问题设计有效的算法，这些问题在许多应用中出现。在这项研究中，研究人员继续长期研究计算几何中的基础和应用问题，包括机器人运动规划问题，计算机图形学中的可见性问题，线性规划的有效算法和其他几何优化问题。这些研究培养和暴露在计算和组合几何的基础研究和各种应用领域，其中一个领域的问题激励新的基本问题，其解决方案反过来又发现在许多其他应用程序的研究之间的丰富的交叉施肥。在几何对象的排列的组合、代数和拓扑分析与相应的有效算法的设计之间有着很强的联系：通常这种算法的算法复杂性（效率）关键取决于其大小或自由度（分别是组合或代数复杂性）。本研究的主要部分致力于研究曲线和曲面的排列。具体而言，它研究（1）与子结构（下包络，单细胞，区域，水平，垂直分解等）相关的组合，拓扑和算法问题。（2）真实的代数几何中计算真实的半代数集的连通分支、分层和维数的相关算法。(3)将这些结果应用于机器人的运动规划、计算机图形学中的各种可见性和相交问题、更高维的广义Voronoi图以及许多几何问题;以及（4）涉及段或曲线的平面布置的组合、拓扑和算法问题，包括图形绘制。这项研究预计将对数学和计算机科学在几何学中的相互作用产生影响，通过在主要会议和讲习班上传播其成果，通过他们编辑的期刊，通过调查人员编写的专著和调查，以及通过他们指导的众多研究生。