Geometric Arrangements and their Algorithmic Applications

计算几何是计算机科学中的一个主要研究领域，其目的是为许多应用中出现的几何性质的问题设计有效的算法。在这项研究中，研究人员继续对计算几何中的基本和应用问题进行长期研究，包括机器人中的运动规划问题、计算机图形学中的可见性问题、线性规划的高效算法以及其他几何优化问题。这些研究培育和揭示了计算和组合几何的基础研究与各种应用领域之间的丰富交叉，其中一个领域的问题激发了对新的基本问题的研究，其解决方案反过来又在许多其他领域得到应用。几何对象排列的组合、代数和拓扑分析与相应高效算法的设计之间有很强的联系：通常，此类算法的算法复杂性(效率)关键取决于尺寸或自由度(组合或代数复杂性)。这项研究的主要部分致力于研究曲线和曲面的排列。具体地说，它研究(1)与子结构(下包络、单胞、区域、层次、垂直分解等)相关的组合、拓扑和算法问题。(3)这些结果在机器人运动规划、计算机图形学中的各种可见性和交集问题、高维广义Voronoi图以及许多几何问题中的应用；以及(4)涉及线段或曲线的平面排列的组合、拓扑和算法问题，包括图形绘制。这项研究预计将通过在主要会议和研讨会、他们一直在编辑的期刊、研究人员一直在撰写的专著和调查以及他们一直在指导的众多研究生中传播其结果，对几何中的数学和计算机科学之间的互动产生影响。

Computational geometry is a major research area in computer science, which aims to design efficient algorithms for problems of geometric nature, which arise in many applications. In this research, the investigators continue their long-term study of basic and applied problems in computational geometry, including motion planning problems in robotics, visibility problems in computer graphics, efficient algorithms for linear programming and other geometric optimization problems. These studies cultivate and expose the rich cross-fertilization between basic research in computational and combinatorial 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 others. There is a strong connection between the combinatorial, algebraic, and topological analysis of arrangements of geometric objects and the design of corresponding efficient algorithms: often the algorithmic complexity (efficiency) of such an algorithm crucially depends on the size or the degree of freedom (combinatorial or algebraic complexity, resp.) of the arrangement.A major portion of this research is devoted to the study of arrangements of curves and surfaces. Specifically, it studies(1) Combinatorial, topological and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions, etc.) in arrangements of surfaces in higher dimensions;(2) Related algorithms in real algebraic geometry for computing connected components, stratifications and the dimension of real semi-algebraic sets.(3) Applications of these results to motion planning in robotics, to various visibility and intersection problems in computer graphics, to generalized Voronoi diagrams in higher dimensions, and to many geometric problems at large; and(4) Combinatorial, topological, and algorithmic problems involving planar arrangements of segments or curves, including graph drawings.This research is expected to have an impact on the interaction between mathematics and computer science in geometry, via the dissemination of its results in major conferences and workshops, the journals that they have been editing, the monographs and surveys that the investigators have been writing, and the numerous graduate students that they have been supervising.