Efficient Geometric Algorithms and Their Applications

计算几何在过去几年中发展非常迅速，因为它在计算机图形学，机器人，VLSI， CAD，实体建模和许多其他领域的应用。该项目的目标是研究应用领域激发的基本几何问题，并探索新的领域，特别强调高维问题和涉及弯曲物体的问题。由于这两个领域都没有得到足够的重视，即使是非常基本的问题也远远没有被理解。重点研究以下几个方面的问题：o射线射击和隐藏面去除；o交点问题；o曲线和曲面的排列；o随机抽样；o动态问题；最短路径及相关问题。预计在本研究中开发的一些算法将相当简单。为了研究这些算法在实际中的性能，我们将对其中的一些算法进行实现。

Computational geometry has developed very rapidly in the last few years because of its applications in areas such as computer graphics, robotics, VLSI, CAD, solid modeling and many others. The goal of this project is to study fundamental geometric problems that are motivated by applied areas and to explore new areas with special emphasis on higher-dimensional problems and on problems involving curved objects. Since both of these areas have not received enough attention, even very basic problems are far from being understood. In particular, problems in the following areas will be investigated: o Ray shooting and hidden surface removal; o Intersection problems; o Arrangements of curves and surfaces; o Random sampling; o Dynamic problems; and o Shortest paths and related problems. It is expected that some of the algorithms developed during this research will be reasonably simple. Some of these algorithms will be implemented in order to study their performance in practice.