权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Exact Computation of the Voronoi Diagram of Polyhedra in Space

空间多面体Voronoi图的精确计算

基本信息

批准号：
190739945
负责人：
Dr. Michael Hemmer
金额：
--
依托单位：
The Blavatnik School of Computer Science
依托单位国家：
德国
项目类别：
Research Fellowships
财政年份：
2011
资助国家：
德国
起止时间：
2010-12-31 至 2012-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/190739945?language=en
关键词：
Exact Computation Voronoi Diagram Polyhedra

项目摘要

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

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