## 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