Studies of Geometric Algorithms and Their Applicatins

几何算法及其应用研究

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

The relatively new field of computational geometry has developed at an accelerating rate in the past few years. The problems that it encompasses cover a wide range of applications, such as motion planning and computer graphics, and their solution often involves the use of sophisticated techniques drawn from many branches of mathematics and theoretical computer science. Prior work includes extensive contributions to many basic and applied problems in the area, including motion planning, hidden surface removal and related visibility problems, combinatorial and algebraic analysis of arrangements of curves and algebraic surfaces, randomized algorithms for linear programming and other optimization problems, etc. The purpose of this research is to continue the work in these fields and to extend it into new core areas in computational geometry. A major portion of the research is devoted to the study of arrangements of curves and surfaces. Specifically, the following problems are being studied: 1. Combinatorial and algorithmic problems related to substructures (lower envelopes, single cells, zones, etc.) in arrangements of surfaces in higher dimensions. 2. Related algorithms in real algebraic geometry for computing cells and road maps in semi-algebraic sets. 3. Combinatorial and algorithmic problems involving planar arrangements of segments or curves (also known as ``geometric graphs''. A theme that is manifest in this work is the rich cross-fertilization between basic research in computational 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 other areas. Another theme is the strong connection between the combinatorial analysis of substructures in arrangements and the design of corresponding efficient algorithms for constructing and utilizing these structures. Often the efficiency of such an algorithm crucially depends on the size of the structure to be computed, and most of the algorithm design has to be devoted to the combinatorial analysis of the complexity of that structure. These considerations are reflected in the work being done.

计算几何这个相对较新的领域在过去几年中正在加速发展。它所包含的问题涵盖了广泛的应用，例如运动规划和计算机图形学，其解决方案通常涉及使用来自数学和理论计算机科学许多分支的复杂技术。之前的工作包括对该领域许多基础和应用问题的广泛贡献，包括运动规划、隐藏表面去除和相关可见性问题、曲线和代数曲面排列的组合和代数分析、线性规划的随机算法和其他优化问题等这项研究的目的是继续这些领域的工作并将其扩展到计算几何的新核心领域。 研究的主要部分致力于研究曲线和曲面的排列。 具体来说，正在研究以下问题： 1.与高维表面排列中的子结构（下封套、单单元、区域等）相关的组合和算法问题。 2. 实代数几何中用于计算半代数集中的单元格和路线图的相关算法。 3.涉及线段或曲线的平面排列（也称为“几何图”）的组合和算法问题。这项工作的一个主题是计算几何基础研究和各个应用领域之间的丰富交叉，一个领域的问题激发了对新基本问题的研究，而这些新的基本问题的解决方案又在许多其他领域得到了应用。另一个主题是排列中子结构的组合分析与构建和利用这些结构的相应有效算法的设计之间的紧密联系。 。通常，这种算法的效率关键取决于要计算的结构的大小，并且大多数算法设计必须致力于该结构的复杂性的组合分析，这些考虑因素反映在正在完成的工作中。