3D Snap Rounding - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2018

3D Snap Rounding

Arrondi d’une soupe de triangles

Résumé

Let $\mathcal{P}$ be a set of $n$ polygons in $\mathbb{R}^3$, each of constant complexity and with pairwise disjoint interiors. We propose a rounding algorithm that maps $\mathcal{P}$ to a simplicial complex $\mathcal{Q}$ whose vertices have integer coordinates. Every face of $\mathcal{P}$ is mapped to a set of faces (or edges or vertices) of $\mathcal{Q}$ and the mapping from $\mathcal{P}$ to $\mathcal{Q}$ can be done through a continuous motion of the faces such that (i) the $L_\infty$ Hausdorff distance between a face and its image during the motion is at most 3/2 and (ii) if two points become equal during the motion, they remain equal through the rest of the motion. In the worse the size of $\mathcal{Q}$ is $O(n^{15})$ and the time complexity of the algorithm is $O(n^{19})$ but, under reasonable hypotheses, these complexities decrease to $O(n^{5})$ and $O(n^{6}\sqrt{n})$.
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}) $.
Fichier principal
Vignette du fichier
RR-9149.pdf (690.36 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (35.76 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

hal-01698928 , version 1 (01-02-2018)

Identifiants

  • HAL Id : hal-01698928 , version 1

Citer

Olivier Devillers, Sylvain Lazard, William Lenhart. 3D Snap Rounding. [Research Report] RR-9149, Inria Nancy - Grand Est. 2018, pp.1-22. ⟨hal-01698928⟩
348 Consultations
87 Téléchargements

Partager

Gmail Facebook X LinkedIn More