A Separation Bound for Real Algebraic Expressions

Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt

Abstract

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.
BibTeX
@inproceedings{burnikel2001separation,
  author = {Christoph Burnikel and Stefan Funke and Kurt Mehlhorn and Stefan Schirra and Susanne Schmitt},
  title = {{A Separation Bound for Real Algebraic Expressions}},
  booktitle = {ESA},
  year = {2001},
  doi = {10.1007/3-540-44676-1\_21},
}

Loading related content...

Figure