Efficient Geometric Algorithms and Their Applications

由于计算几何在计算机图形学、机器人学、超大规模集成电路、计算机辅助设计、实体造型等领域的应用，在过去的几年里发展非常迅速。这个项目的目标是研究由应用领域驱动的基本几何问题，并探索新的领域，特别强调高维问题和涉及曲线对象的问题。由于这两个方面都没有得到足够的重视，即使是最基本的问题也远远没有得到理解。特别是，将调查以下领域的问题：o射线拍摄和隐藏面消除；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.