Designing Geometric Algorithms with Correct Rounded Arithmetic Implementations

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

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.