Fast and Accurate Computations with Algebraic Primitives and Predicates

to linear primitives. It is based on exact computation paradigm that uses
rational arithmetic for the underlying computations. There is a general
perception that extending "exact computation paradigm" to non-linear problems
is impractical and very hard to implement.

I describe some approaches for accurate evaluation of algebraic predicates,
root isolation of polynomial systems, and exact manipulation of algebraic
points and curves for geometric applications. The set of applications
include boundary evaluation of low degree algebraic solids, medial
axis computations, computing curve arrangements etc. Based on these
algorithms, I will describe two libraries, MAPC and PRECISE, which can be used
for different geometric applications. The next major challenge is to develop
approaches to handle degeneracies.