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.)