Simple and Efficient Geometric Algorithms and Their Applications

在计算机图形学、机器人学、计算机视觉、计算机辅助设计、图像处理和地理信息系统等多个应用领域的问题的推动下，计算几何在大约20年前成为一门学科。许多高效的几何算法和复杂的算法范例已经被开发出来，计算几何到现在已经是一门丰富和成熟的学科。然而，计算几何和应用领域之间的联系仍然不像人们所希望的那样强烈。该项目的目的是缩小几何与相关应用领域之间的差距。该项目将解决传统算法设计框架之外的问题，并将开发和实施在实践中运行良好的简单算法。几何问题的各种应用领域，包括可视化，机器人，数据挖掘和计量学将被研究。这些算法将在更现实的计算模型中进行开发和分析，并将在“真实”输入上进行实施和测试。

Motivated by problems in several applied areas, such as computer graphics, robotics, computer vision, computer aided design, image processing, and geographic information systems, computational geometry emerged as a discipline about twenty years ago. Numerous efficient geometric algorithms and sophisticated algorithmic paradigms have been developed, and computational geometry is by now a rich and mature discipline. The link between computational geometry and application areas is, however, still not as strong as one would have hoped for. The purpose of this project is to narrow the gap between geometry and the related applied areas. The project will address the issues beyond the traditional framework of algorithmic design, and simple algorithms will be developed and implemented that work well in practice. Geometric problems motivated by various application areas, including visualization, robotics, data mining, and metrology will be studied. The algorithms will be developed and analyzed in a more realistic model of computation and will be implemented and tested on ``real'' inputs.