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. 涉及平面的组合和算法问题 线段或曲线的排列（也称为“几何图形”）。 一 这部作品的主题是丰富的交叉施肥， 在计算几何和各种应用领域的基础研究， 一个领域的问题激发了对新的基本问题的研究， 这种解决方案又在许多其他领域得到应用。 另一个主题是 子结构的组合分析之间的强联系， 安排和设计相应的有效算法， 构建和利用这些结构。 通常这种算法的效率 关键取决于要计算的结构的大小， 算法设计必须致力于组合分析， 这种结构的复杂性。这些考虑反映在工作中 正在做。