Geometric Arrangements and their Algorithmic Applications

摘要许多几何算法的算法复杂度（效率）主要取决于待计算结构的大小（组合复杂度）。首席研究员研究机器人、计算机图形学、蜂窝网络、生物信息学等领域的各种问题。，属于这一类。为了约束相应结构的复杂性，他们通常需要从数学和理论计算机科学的几个分支中汲取复杂的技术。在大多数情况下，大部分工作都致力于研究欧几里德空间中曲线和曲面的排列，这是该领域的核心。在此过程中，他们在几个经典数学学科中发展了重要的新结果，从Hellytheory到turan - and Ramsey-type极值图论。具体来说，pi正在研究：(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