A Complete Implementation for Computing General Dimensional Convex Hulls

Ioannis Z. Emiris 1
1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We study two important, and often complementary, issues in the implementation of geometric algorithms, namely exact arithmetic and degeneracy. We focus on integer arithmetic and propose a general and efficient method for its implementation based on modular arithmetic. We suggest that {\em probabilistic modular arithmetic} may be of wide interest, as it combines the advantages of modular arithmetic with randomization in order to speed up the lifting of residues to an integer. We derive general error bounds and discuss the implementation of this approach in our general-dimension convex hull program. The use of perturbations as a method to cope with input degeneracy is also illustrated. We present the implementation of a computationally efficient scheme that, moreover, greatly simplifies the task of programming. We concentrate on {\em postprocessing}, often perceived as the Achilles' heel of perturbations. Starting in the context of a specific application in robotics, we examine the complexity of postprocessing and attempt to delimit the cases where perturbations become a hindrance rather than an enhancement. Lastly, we discuss the visualization capabilities of our software and illustrate them for problems in computational algebraic geometry.
Type de document :
RR-2551, INRIA. 1995
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:34:40
Dernière modification le : mercredi 17 octobre 2018 - 17:02:07
Document(s) archivé(s) le : jeudi 24 mars 2011 - 14:19:34



  • HAL Id : inria-00074129, version 1



Ioannis Z. Emiris. A Complete Implementation for Computing General Dimensional Convex Hulls. RR-2551, INRIA. 1995. 〈inria-00074129〉



Consultations de la notice


Téléchargements de fichiers