The Design and Implementation of Geometric Algorithms

将在计算几何的三个广泛领域进行研究。这些领域涵盖了从实施和调试几何算法时出现的实际考虑到算法设计中出现的理论问题和下限证明。它们包括算法的设计和分析，主要集中在涉及二维以上的非线性曲面的问题，特别是隐藏曲面的去除、实代数变体的三角剖分和多维搜索，建立一个实现几何算法和工具的环境，最终可供研究人员用于生产和共享几何软件。以及设计稳健的几何算法，这需要解决有限精度算术以及常见现实世界几何数据的简并性所引起的问题。

Research in three broad areas of computational geometry will be conducted. These areas cover the spectrum from practical considerations which arise when implementing and debugging geometric algorithms to theoretical questions arising in algorithm design and lower bound proofs. They include design and analysis of algorithms, concentrating mostly on problems involving nonlinear surfaces in dimensions higher than two, in particular, hidden surface removal, triangulations of real-algebraic varieties, and multidimensional searching, building an environment for implementing geometric algorithms and tools which can ultimately be used by researchers to produce and share geometric software, and design of robust geometric algorithms which entails tackling problems arising from finite precision arithmetic as well as the degeneracy of common real world geometric data.