| In conjunction with Victor Milenkovic (U. Miami), we are developing a theoretical model of robust computational geometry with floating point arithmetic. Computational geometry is the branch of theoretical computer science that develops efficient algorithms for geometric queries and constructions. This is a core research problem with numerous applications in science and in industry. The robustness problem is to implement geometric algorithms with computer arithmetic. Geometric algorithms make decisions based on the signs of real valued expressions. Floating point can yield inconsistent or incorrect decisions when expressions are near zero. Rational arithmetic does not have these problems, but the evaluation time is exponential in the depth of the expression tree, which leads to unacceptable performance on large problems. We solve the inconsistency problem of floating point in an efficient manner by incorporating into the theoretical model the empirical fact that inconsistencies are rare. We develop algorithms that are efficient on real inputs and that satisfy formal run-time bounds for all inputs. The main project goal is a robust algorithm for configuration space construction, which is a core computational geometry task with many applications. |
