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

项目摘要许多几何算法的算法复杂性（效率）主要取决于要计算的结构的大小（组合复杂性），主要研究人员研究源自机器人学、计算机图形学、细胞网络、生物信息学等的各种问题。为了限制相应结构的复杂性，它们通常需要来自数学和理论计算机科学的多个分支的复杂技术。在大多数情况下，大部分工作致力于研究排列。欧几里得空间中的曲线和曲面的研究是该领域的核心，在此过程中，他们在从Helly理论到图兰型和拉姆齐型极值图论等几个经典数学学科中取得了重要的新成果。 PI正在研究：（1）与较高层表面的排列结构（下层包络线和单元、水平、垂直分解、与点的重合等）相关的组合、拓扑和算法问题(2) 将这些结果应用于几何优化和范围搜索、计算机图形学中的各种可见性和相交问题、更高维度的广义 Voronoi 图、机器人中的运动规划以及许多其他广泛的几何问题(3) 涉及线段或曲线的平面排列的组合、拓扑和算法问题，包括图形绘制。1