A Separation Bound for Real Algebraic Expressions
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt · Lecture notes in computer science · 2001
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 .