3D Snap Rounding

Olivier Devillers 1 Sylvain Lazard 1 William Lenhart 2
1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Résumé : Soit $\mathcal{P}$ un ensemble de $n$ polygones dans $\mathbb{R}^3$, chacun de complexité constante, et d'intérieurs disjoints. Nous présentons un algorithme d'arrondi tel que l'image de $\mathcal{P}$ soit un complexe simplicial $\mathcal{Q}$ dont les sommets ont des coordonnées entières. Chaque face de$\mathcal{P}$ est envoyée sur un ensemble de faces (ou arêtes ou sommets) de $\mathcal{Q}$ et, de plus, $\mathcal {P}$ peut être tranformé en $\mathcal {Q}$ par un mouvement continu des faces de telle sorte que (i) la distance de Hausdorff $L_\infty$ entre une face et son image pendant le mouvement est au plus $3/2$ et (ii) si deux points deviennent égaux pendant le mouvement, ils restent égaux durant le reste de le mouvement. La taille de $\mathcal {Q}$ est au pire $ O (n ^ {15}) $ et la complexité temporelle de l'algorithme est $ O (n ^ {19}) $. Cependant, sous des hypothèses raisonnables, ces complexités peuvent être ramenées à $ O (n ^ {5}) $ et $ O (n ^ {6} \sqrt {n}) $.
Type de document :
Rapport
[Research Report] RR-9149, Inria Nancy - Grand Est. 2018, pp.1-22
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01698928
Contributeur : Olivier Devillers <>
Soumis le : jeudi 1 février 2018 - 17:39:05
Dernière modification le : jeudi 8 février 2018 - 17:19:34
Document(s) archivé(s) le : vendredi 25 mai 2018 - 16:37:18

Fichiers

RR-9149.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01698928, version 1

Citation

Olivier Devillers, Sylvain Lazard, William Lenhart. 3D Snap Rounding. [Research Report] RR-9149, Inria Nancy - Grand Est. 2018, pp.1-22. 〈hal-01698928〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

46