Studies of Geometric Algorithms and Their Applications

这个项目将主要研究曲线和曲面的排列。具体来说，它将研究与高维曲面排列中的子结构（低层包膜、单细胞、区域、水平、垂直分解等）相关的组合和算法问题。实代数几何中计算连通分量、分层和实半代数集维数的相关算法。将这些结果应用于机器人的运动规划，计算机图形学中的各种可见性和交叉问题，高维的广义Voronoi图以及许多几何问题。涉及线段或曲线（也称为几何图形）的平面排列的组合和算法问题。

This project will mainly investigate arrangements of curves and surfaces. Specifically, it will study Combinatorial and algorithmic problems related to substructures (lower envelopes, single cells, zones, levels, vertical decompositions, etc.) in arrangements of surfaces in higher dimensions.Related algorithms in real algebraic geometry for computing connected components, stratifications and the dimension of real semi-algebraic sets.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.Combinatorial and algorithmic problems involving planar arrangements of segments or curves (also known as geometric graphs.)