Geometric Arrangements and their Algorithmic Applications

项目摘要许多几何算法的算法复杂度(效率)主要取决于要计算的结构的大小(组合复杂度)。首席调查员研究各种起源于机器人学、计算机图形学、蜂窝网络、生物信息学等属于这一类别的问题。为了限制相应结构的复杂性，它们通常需要从数学和理论计算机科学的几个分支中提取复杂的技术。在大多数情况下，大部分工作致力于研究欧氏空间中曲线和曲面的排列，这是该领域的核心。在这个过程中，他们在几个经典数学学科中得出了重要的新结果，从希腊论到图尔安和拉姆齐型极值图论。具体地说，私人投资机构正在研究：(1)与排列中的结构有关的组合、拓扑和算法问题(较低的包络和单元、级别、垂直分解、与点的关联等)。(2)这些结果在几何优化和范围搜索、计算机图形学中的各种可见性和交集问题、高维的广义Voronoi图、机器人中的运动规划以及许多其他几何问题中的应用。(3)涉及分段或曲线的平面布置的组合、拓扑和算法问题，包括图形绘制

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