Constructive root bound for k-ary rational input numbers - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2006

Constructive root bound for k-ary rational input numbers

Résumé

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.
Fichier principal
Vignette du fichier
p.pdf (272.84 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00344349 , version 1 (04-12-2008)

Identifiants

Citer

Sylvain Pion, Chee Yap. Constructive root bound for k-ary rational input numbers. Theoretical Computer Science, 2006, 369 (1-3), pp.361-376. ⟨10.1016/j.tcs.2006.09.010⟩. ⟨inria-00344349⟩
76 Consultations
674 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More