Geometric Arrangements and their Algorithmic Applications

计算几何是计算机科学的一个重要研究领域，它旨在为许多应用中出现的几何性质的问题设计有效的算法。在这项研究中，研究人员继续他们对计算几何的基础和应用问题的长期研究，包括机器人中的运动规划问题，计算机图形学中的可见性问题，线性规划的有效算法和其他几何优化问题。这些研究培养并揭示了计算几何和组合几何的基础研究与各种应用领域之间的丰富的交叉施肥，其中一个领域的问题激发了对新的基本问题的研究，这些问题的解决反过来又在许多其他领域找到了应用。几何对象排列的组合、代数和拓扑分析与相应高效算法的设计之间存在着密切的联系：通常这种算法的算法复杂性（效率）关键取决于排列的大小或自由度（组合或代数复杂性）。这项研究的主要部分是研究曲线和曲面的排列。具体而言，它研究(1)与高维曲面排列中的子结构（下层包膜、单细胞、区域、水平、垂直分解等）相关的组合、拓扑和算法问题；(2)实代数几何中计算连通分量、分层和实半代数集维数的相关算法。(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.