AF:Small:Collaborative Research:Making Computational Geometry Polynomial in Derivation Length and in Dimension

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

Computational geometry is the discipline that creates algorithms todesign 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, thecomputer sees only numbers -- and usually, for speed, onlyapproximate, "floating-point" numbers. E.g., points on a line thatare represented as numerical coordinates, when rounded to thenumber of digits the computer stores, may no longer lie on any commonline. Subsequent calculations that rely on a line being straight ortwo lines intersecting at most once can then go badly astray. Errorin numerical computation can sometimes be limited by rounding, butthere is no practical technique for rounding three-dimensional shapes.This project investigates shape rounding by encasement:High-complexity shapes are encased in approximating polyhedra withfloating-point vertex coordinates. Given an encasement, the PIs havedescribed a rounding algorithm that projects input features to nearbyencasement features. For dealing with intersections of surfaces, theproject creates output-sensitive algorithms for another type ofencasement, an isolating encasement that can have distant boundaryvertices but cannot encase other features.Encasement is only part of the solution, so the project also exploresways to compute topological structure using bounded-complexityarithmetic by avoiding numerical computation for the degenerate (zero)expressions. It investigates using graph theory to analyze explicitexpressions and algebraic techniques to analyze expressions involvingroots of polynomials.The outcome is to include a software library for implementingcomputational geometry algorithms with automated shape rounding. Theproject integrates education and research through an introductorycomputational geometry course in which standard algorithms are taughtand implemented using the library. Previously, the computational costof multi-step algorithms forced students to consider each algorithm inisolation.