Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision

Abstract : 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. Our method relies on modular computations, for which comparisons are usually thought to require multiprecision. Our novel technique of {\it recursive relaxation of the moduli} enables us to carry out sign determination and comparisons by using only floating point computations in single precision. This leads us to propose a hybrid symbolic-numeric approach to exact arithmetic. The method is highly parallelizable and is the fastest of all known multiprecision methods \from a complexity point of view. As an application, we show how to compute a few geometric predicates that reduce to matrix determinants and we discuss implementation efficiency, which can be enhanced by arithmetic filters. We substantiate these claims by experimental results and comparisons to other existing approaches. Our method can be used to generate robust and efficient implementations of geometric algorithms (convex hulls, Delaunay triangulations, arrangements) and numerical computer algebra (algebraic representation of curves and points, symbolic perturbation, Sturm sequences and multivariate resultants).
Type de document :
Rapport
RR-3213, INRIA. 1997
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00073476
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:57:13
Dernière modification le : jeudi 11 janvier 2018 - 17:02:47
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:31:21

Fichiers

Identifiants

  • HAL Id : inria-00073476, version 1

Collections

Citation

Hervé Brönnimann, Ioannis Z. Emiris, Victor Y. Pan, Sylvain Pion. Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision. RR-3213, INRIA. 1997. 〈inria-00073476〉

Partager

Métriques

Consultations de la notice

206

Téléchargements de fichiers

128