Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A separation bound for real algebraic expressions
Burnikel C., Funke S., Mehlhorn K., Schirra S., Schmitt S. Algorithmica55 (1):14-28,2009.Type:Article
Date Reviewed: Apr 5 2010

This paper is concerned with separation bounds--how small can a nonzero number defined by a certain kind of expression be? Put another way, how accurate do we need to be to answer with positive, negative, or zero? Such questions are fundamental to computational geometry, since getting them wrong can lead to structures that are topologically incoherent. The starting point is a bound [1] for expressions involving the four arithmetic operations and radicals.

This bound is extended to include “the k-th real root of a polynomial,” and is made linear even if division is present. The key to this improvement lies in, for example, writing √a/b as aab rather than √a/√b. The authors compare their bound with the previous one [1] and one from Li and Yap’s paper [2]; however, their new bound is both theoretically and practically incomparable with the latter, since Li and Yap’s bound is sometimes better and sometimes worse.

It should be noted: although the paper’s title refers to real expressions, the methodology is equally applicable to complex ones. Also, “log” means “log2” throughout the paper, and the authors sometimes optimize out divisions for the older work [1].

Reviewer:  J. H. Davenport Review #: CR137889 (1008-0835)
1) Burnikel, C.; Fleischer, R.; Mehlhorn, K.; Schirra, S. A strong and easily computable separation bound for arithmetic expressions involving square roots. Algorithmica 27, 1(2000), 87–99.
2) Li, C.; Yap, C. A new constructive root bound for algebraic expressions. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms SIAM, 2001, 496–505.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Expressions And Their Representation (I.1.1 )
 
 
Computer-Aided Design (CAD) (J.6 ... )
 
 
Representations (General And Polynomial) (I.1.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Expressions And Their Representation": Date
Unification theory
Siekmann J. Journal of Symbolic Computation 7(3-4): 207-274, 1989. Type: Article
Mar 1 1990
Boolean unification--the story so far
Martin U., Nipkow T. (ed) Journal of Symbolic Computation 7(3-4): 275-293, 1989. Type: Article
Mar 1 1990
Subresultants under composition
Hong H. Journal of Symbolic Computation 23(4): 355-365, 1997. Type: Article
Apr 1 1998
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy