Exact Computation of the Voronoi Diagram of Polyhedra in Space

计算几何的一个重要研究动机是许多几何算法，例如在计算机辅助设计系统中使用的算法，实际上不是鲁棒的。通常，这是由使用快速但不精确的浮点运算引起的。例如，很难判断两个物体是仅仅靠得很近，还是实际上彼此接触。这可能导致算法中的错误（和不一致）决策，甚至可能导致系统完全崩溃。计算机代数已经开发出非常通用和精确的工具，可以在原则上解决这些问题，但这些工具的幼稚应用迄今为止太慢，无法在实践中使用。因此，我们的主要研究兴趣是结合计算几何，实体建模和计算机代数的最佳方法，以设计和实现精确，完整和高效的几何算法（前两个意味着鲁棒性）。在这种背景下，我们决定将注意力集中在计算几何中的一个基本数据结构上，即Voronoi图。对于一组输入对象，Voronoi图是将空间分解为单元，使得每个Voronoi单元精确地包含与特定对象更接近的所有点，而不是与所有其他对象更接近的点。我们的目标是开发和实现一种高效、精确和完整的算法，用于计算三维空间中一组多面体物体的Voronoi图。据我们所知，这将是第一个精确、完整、健壮的算法，可以计算三维多面体的Voronoi图。虽然结构本身很重要，但我们预计，我们项目的成功完成将对稳健实施复杂的三维几何结构的可行性产生更广泛的影响，这一领域的发展不如二维几何结构那么好

An important research motivation in Computational Geometry is that many geometric algorithms, for instance used in Computer Aided Design systems, are actually not robust.Often, this is caused by the use of fast but inexact floating point arithmetic. For instance, it is very hard to decide whether two objects just come very close or whether they actually touch each other. This can lead to wrong (and inconsistent) decisions within algorithms which may even lead to a full crash of the system.Computer Algebra has developed very general and exact tools that could solve such problems in principle, but a naive application of these tools is by far too slow to be used in practice. Our cardinal research interest is thus to incorporate the bestmethods from Computational Geometry, Solid Modeling and Computer Algebra in order to design and implement geometric algorithms that are exact, complete and efficient (the first two imply robustness).In this context we decided to focus our attention towards a fundamental data structure in Computational Geometry, the Voronoi Diagram. For a set of input objects the Voronoi diagram is the decomposition of the space into cells such that each Voronoi cell exactly contains all points that are closer to a particular object than to all other objects. Our ambition is to develop and implement an efficient, exact and complete algorithm that computes the Voronoi diagram of a set of polyhedral objects in three-dimensional space.To the best of our knowledge this would be the first exact and complete, and thus robust, algorithm that computes the Voronoi diagram for polyhedra in three dimensions.While the structure is important in its own right, we anticipate that the successful completion of our project will have wider impact on the feasibility of robustly implementing complex three-dimensional geometric structures,an area that is not as well developed as its two-dimensional counterpart