robust computational geometry

Project member? Login to members area.


Computational geometry algorithms are hard to implement robustly and efficiently.   One problem is that the control logic is expressed in terms of the signs of predicate polynomials.   The polynomials must be evaluated exactly, since any numerical error can cause an incorrect sign and hence a large output error.   Degenerate (zero) values must be detected and they often entail special case logic.   Bit complexity must be controlled in iterated computations by rounding, typically to double float, while preserving combinatorial properties.  Curved (nonlinear) geometry must be manipulated despite its  high algebraic degree.   Milenkovic and I have solved some of these problems and are working on the others.


The Purdue University Research Repository (PURR) is a university core research facility provided by the Purdue University Libraries, the Office of the Executive Vice President for Research and Partnerships, and Information Technology at Purdue (ITaP).