Studies of Geometric Arrangements and their Algorithmic Applications

计算几何涵盖了广泛的应用，如运动规划和计算机图形学，它对解决这些问题的贡献涉及到使用从数学和计算机科学的许多分支中提取的复杂技术。研究人员广泛研究了该领域的许多基础和应用问题，包括运动规划、Voronoi图、曲线和代数曲面排列的组合和代数分析、图形绘制、随机算法和几何优化。这项研究的主要部分涉及对曲线和曲面排列的研究。在过去的15年中，PI在这些问题上取得了重大进展，开辟了许多新的具有挑战性的研究方向，包括：与高维表面排列中的子结构（低层包膜、单细胞、区域、水平、垂直分解）相关的组合和算法问题。实代数几何中计算连通分量、分层、实半代数集的维数和其他拓扑参数的相关算法。图形绘制和其他算法、组合和拓扑问题，涉及段或曲线的平面排列。这些结果在许多领域的应用，包括机器人的运动规划，计算机图形学中的渲染和建模问题，广义Voronoi图和几何优化问题，包括计量和设施定位问题。这一研究的一个重要特点是计算几何和组合几何的基础研究与各种应用领域的交叉施肥。另一个主题是排列组合分析和有效算法设计之间的紧密联系，以构建和利用这些结构。算法的效率往往关键取决于要计算的结构的大小，而大部分工作都致力于限制这个数量。

Computational geometry covers a wide range of applications, such as motion planning and computer graphics, and its contribution to their solution involves the use of sophisticated techniques drawn from many branches of mathematics and computer science. The investigators extensively study many basic and applied problems in the area, including motion planning, Voronoi diagrams, combinatorial and algebraic analysis of arrangements of curves and algebraic surfaces, graph drawing, randomized algorithms, and geometric optimization.A major portion of this research involves the study of arrangements of curves and surfaces. The significant progress made by the PI's on these problems during the past 15 years has opened up many new challenging research directions, including:Combinatorial and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions) in arrangements of surfaces in higher dimensions. Related algorithms in real algebraic geometry for computing connected components, stratifications, the dimension and othertopological parameters of real semi-algebraic sets. Graph drawing and other algorithmic, combinatorial, and topological problems involving planar arrangements of segments or curves. Applications of these results to numerous areas, including motion planning in robotics, rendering and modeling problems in computer graphics, generalized Voronoi diagrams and geometric optimization problems, including problems in metrology and facility location. An important feature of this research is the cross-fertilization between basic research in computational and combinatorial geometry and various application areas. Another theme is the strong connection between the combinatorial analysis of arrangements and the design of efficient algorithms for constructing and utilizing these structures. The efficiency of the algorithms often crucially depends on the size of the structure to be computed, and most of the work is devoted to bounding this quantity.