Studies of Geometric Algorithms and Their Applications

点击翻译按钮获取中文摘要

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