Constructive root bound for k-ary rational input numbers

Abstract : 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.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2006, 369 (1-3), pp.361-376. 〈10.1016/j.tcs.2006.09.010〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00344349
Contributeur : Sylvain Pion <>
Soumis le : jeudi 4 décembre 2008 - 16:03:46
Dernière modification le : jeudi 11 janvier 2018 - 17:02:47
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:44:40

Fichier

p.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sylvain Pion, Chee Yap. Constructive root bound for k-ary rational input numbers. Journal of Theoretical Computer Science (TCS), Elsevier, 2006, 369 (1-3), pp.361-376. 〈10.1016/j.tcs.2006.09.010〉. 〈inria-00344349〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

153