Efficient Geometric Algorithms and Their Applications

由于其在计算机图形学、机器人技术、VLSI、CAD、实体建模等领域的应用，计算几何在过去几年中发展非常迅速。 该项目的目标是研究由应用领域引发的基本几何问题，并探索新领域，特别强调高维问题和涉及弯曲物体的问题。 由于这两个领域都没有受到足够的重视，即使是非常基本的问题也远未被理解。 特别是，将调查以下领域的问题： 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.