s'authentifier
version française rss feed

inria-00344963, version 1

Computing exact geometric predicates using modular arithmetic with single precision

Hervé Brönnimann () a1, Ioannis Z. Emiris 2, Victor Y. Y. Pan b3, Sylvain Pion () 1

ACM Symposium on Computational Geometry (SCG) (1997) 174-182

Résumé : We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric algorithms depends. The method relies on modular computations, for which comparisons are usually thought to require multiprecision. Our novel technique of recursive relaxation of the moduli enables us to carry out sign determination and comparisons by using only floating point computations in single precision. The method is highly parallelizable and is the fastest of all known multiprecision methods from a complexity point of view. We show how to compute a few geometric predicates that reduce to matrix determinants. We discuss implementation efficiency, which can be enhanced by good arithmetic filters. We substantiate these claims by experimental results and comparisons to other existing approaches. This method can be used to generate robust and efficient implementations of geometric algorithms, including solid modeling, manufacturing and tolerancing, and numerical computer algebra (algebraic representation of curves and points, symbolic perturbation, Sturm sequences and multivariate resultants).

  • Domaine : Informatique/Géométrie algorithmique
    Informatique/Arithmétique des ordinateurs
  • Mots-clés : computational geometry – exact arithmetic – robustness – modular computations – single precision – Residue Number Systems (RNS)
 
  • inria-00344963, version 1
  • oai:hal.inria.fr:inria-00344963
  • Contributeur : 
  • Soumis le : Lundi 8 Décembre 2008, 01:07:30
  • Dernière modification le : Mardi 10 Juillet 2012, 16:16:47
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
  翻译: