TY - JOUR
T1 - Constructive root bound for k-ary rational input numbers
AU - Pion, Sylvain
AU - Yap, Chee K.
N1 - Funding Information:
This research is supported by NSF/ITR Grant #CCR-0082056. Sylvain’s work is conducted under a postdoc fellowship with this grant. ∗ Corresponding author. Tel.: +33 492385025; fax: +33 492387683. E-mail addresses: [email protected] (S. Pion), [email protected] (C.K. Yap).
PY - 2006/12/15
Y1 - 2006/12/15
N2 - Guaranteeing accuracy is the critical capability in exact geometric computation, an important paradigm for constructing robust geometric algorithms. Constructive root bounds is the fundamental technique needed to achieve such guaranteed accuracy. Current bounds are overly pessimistic in the presence of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since a majority of input numbers in scientific and engineering applications are either binary (k = 2) or decimal (k = 10), our results could lead to a significant speedup for a large class of applications. We apply our method to two of the best available constructive root bounds, the BFMSS Bound and the Degree-Measure Bound. Implementation and experimental results based on the Core Library are reported.
AB - Guaranteeing accuracy is the critical capability in exact geometric computation, an important paradigm for constructing robust geometric algorithms. Constructive root bounds is the fundamental technique needed to achieve such guaranteed accuracy. Current bounds are overly pessimistic in the presence of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since a majority of input numbers in scientific and engineering applications are either binary (k = 2) or decimal (k = 10), our results could lead to a significant speedup for a large class of applications. We apply our method to two of the best available constructive root bounds, the BFMSS Bound and the Degree-Measure Bound. Implementation and experimental results based on the Core Library are reported.
KW - Constructive root bounds
KW - Exact geometric computation
KW - Robust numerical algorithms
KW - k-Ary rational numbers
UR - http://www.scopus.com/inward/record.url?scp=33751020582&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33751020582&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2006.09.010
DO - 10.1016/j.tcs.2006.09.010
M3 - Article
AN - SCOPUS:33751020582
SN - 0304-3975
VL - 369
SP - 361
EP - 376
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -