Degeneracy in Geometric Computation

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

Today, geometric data and geometric structures are used in almost all branches of science, if only in the display of results and data. In the majority of the applications, the geometric data is inherently degenerate in the sense that it is very different from data obtained in a random fashion. Unfortunately, degenerate configurations often bring about serious robustness and correctness problems for computer programs that manipulate the data. The two main reasons for this weakness of current software are the bizarre structure of the space of degeneracies and the accuracy problems that arise if we attempt to detect and classify degenrate configurations. This research is a systematic study of degeneracy in geometric data that spans the investigation of its combinatorial structure, the computational complexity of determining degeneracy, and - most importantly - systematic ways to cope with degenerate data.