Designing Geometric Algorithms with Correct Rounded Arithmetic Implementations

使用四舍五入算法实现的几何算法通常是不可靠的。不幸的是，精确的算术是不切实际的，并且需要花费大量的开发时间来修改几何程序来处理舍入误差，永远无法达到绝对的可靠性。研究将在鲁棒几何领域进行：具有可证明的正确的四舍五入算术实现的几何算法的规范和创建。在本项目所遵循的严格鲁棒性方法下，算法也是可行和准确的，这意味着它们生成的有效几何对象接近确切的答案。利用称为xy单调推理和高级舍入的技术，研究者最近提出了在平面多边形区域上准确有效地执行集合操作和欧几里得变换的任何组合的算法。严格稳健的算法现在将开发用于构建以下对象：多维点的凸包和Voronoi图，多面体的Voronoi图以及多面体区域的交叉点。这些对象具有重要的应用，其中包括实体建模和有限元分析网格的自动生成。此外，从创建这些算法中获得的经验有望为创建其他鲁棒算法提供基础。

Geometric algorithms, when implemented using rounded arithmetic, are generally unreliable. Unfortunately, exact arithmetic is impractical, and much development time is spent modifying geometric programs to deal with round-off error, never reaching absolute reliability. Investigation will be carried out in the area of robust geometry: the specification and creation of geometric algorithms with provably correct rounded arithmetic implementations. Under the strict robustness approach followed in this project, algorithms are also feasible and accurate, meaning that they generate valid geometric objects close to the exact answer. Employing techniques called xy- monotonic reasoning and high level rounding, the investigator has recently presented algorithms for accurately and efficiently performing any combination of set operations and Euclidean transformations on polygonal regions in the plane. Strictly robust algorithms will now be developed for constructing the following objects: convex hulls and Voronoi diagrams of points in multiple dimensions, Voronoi diagrams of polyhedra, and intersections of polyhedral regions. These objects have important applications, among them the modeling of solids and the automatic generation of meshes for finite element analysis. In addition, the experience gained from the creation of these algorithms is expected to provide a basis for the creation of other robust algorithms.