Exact Computation of the Voronoi Diagram of Polyhedra in Space

点击翻译按钮获取中文摘要

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