A Separation Bound for Real Algebraic Expressions
Christop Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions
whose leaves are integers
and whose internal nodes are additions, subtractions, multiplications,
divisions, $k$-th root operations for integral $k$, and taking roots of
polynomials whose coefficients are given by the values of subexpressions.
We consider the sign computation of real algebraic
expressions, a task vital for the implementation of geometric algorithms.
We prove a new separation bound for
real algebraic expressions and compare it analytically and experimentally with
previous bounds. The
bound is used in the sign test of the number type
leda_real.
PDF