Geometric Arrangements and their Algorithmic Applications

几何排列及其算法应用

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

Project AbstractThe algorithmic complexity (efficiency) of many geometric algorithms depends mainly on the size(combinatorial complexity) of the structure to be computed. The Principal Investigators study avariety of problems originating in robotics, computer graphics, cellular networking, bioinformatics,etc., that belong to this category. To bound the complexity of the corresponding structures, theyoften need sophisticated techniques drawn from several branches of mathematics and theoreticalcomputer science. In most cases, the bulk of the work is devoted to the study of arrangements ofcurves and surfaces in Euclidean spaces, which lies at the heart of the field. During the process,they develop important new results in several classical mathematical disciplines ranging from Hellytheory to Tur´an- and Ramsey-type extremal graph theory. Specifically, the PIs are studying:(1) Combinatorial, topological and algorithmic problems related to structures in arrangements(lower envelopes and cells, levels, vertical decompositions, incidences with points, etc.) of surfacesin higher dimensions.(2) Applications of these results to geometric optimization and range searching, to various visi-bility and intersection problems in computer graphics, to generalized Voronoi diagrams in higherdimensions, to motion planning in robotics, and to many other geometric problems at large.(3) Combinatorial, topological, and algorithmic problems involving planar arrangements of seg-ments or curves, including graph drawings.1

许多几何算法的算法复杂性（效率）主要取决于要计算的结构的大小（组合复杂性）。主要研究人员研究各种各样的问题，起源于机器人技术，计算机图形学，细胞网络，生物信息学等，都属于这一类。为了限制相应结构的复杂性，它们通常需要从数学和理论计算机科学的几个分支中提取的复杂技术。在大多数情况下，大部分的工作是专门研究的安排ofcurves和曲面在欧几里德空间，这是在心脏领域。在这个过程中，他们在几个经典数学学科中取得了重要的新成果，从Hellytheory到Tur 'an和Ramsey型极值图论。具体而言，PI正在研究：（1）与排列结构相关的组合，拓扑和算法问题（下包络和单元，水平，垂直分解，与点的关联等）。of surfaces表面in higher高dimensions尺寸. (2)这些结果的应用几何优化和范围搜索，在计算机图形学中的各种可扩展性和交叉问题，广义Voronoi图在higherdimensions，在机器人运动规划，以及许多其他几何问题的大。(3)涉及线段或曲线的平面排列的组合、拓扑和算法问题，包括图形学。