Computational geometry is the discipline that creates algorithms to design and manipulate shapes. It has wide application in science, engineering, and industry -- CAD/CAM systems are a notable example. The problem is, where we see shapes and their spatial relations, the computer sees only numbers -- and usually, for speed, only approximate, "floating-point" numbers. E.g., points on a line that are represented as numerical coordinates, when rounded to the number of digits the computer stores, may no longer lie on any common line. Subsequent calculations that rely on a line being straight or two lines intersecting at most once can then go badly astray. Error in numerical computation can sometimes be limited by rounding, but there is no practical technique for rounding three-dimensional shapes.
This project investigates shape rounding by encasement: High-complexity shapes are encased in approximating polyhedra with floating-point vertex coordinates. Given an encasement, the PIs have described a rounding algorithm that projects input features to nearby encasement features. For dealing with intersections of surfaces, the project creates output-sensitive algorithms for another type of encasement, an isolating encasement that can have distant boundary vertices but cannot encase other features.
Encasement is only part of the solution, so the project also explores ways to compute topological structure using bounded-complexity arithmetic by avoiding numerical computation for the degenerate (zero) expressions. It investigates using graph theory to analyze explicit expressions and algebraic techniques to analyze expressions involving roots of polynomials.
The outcome is to include a software library for implementing computational geometry algorithms with automated shape rounding. The project integrates education and research through an introductory computational geometry course in which standard algorithms are taught and implemented using the library. Previously, the computational cost of multi-step algorithms forced students to consider each algorithm in isolation.
