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
Abstract : 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 worst case, 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})$.
Type de document :
Communication dans un congrès
SoCG 2018 - 34th International Symposium on Computational Geometry , Jun 2018, Budapest, Hungary. pp.30:1 - 30:14, 〈10.4230/LIPIcs.SoCG.2018.30〉
Liste complète des métadonnées


https://hal.inria.fr/hal-01727375
Contributeur : Olivier Devillers <>
Soumis le : vendredi 9 mars 2018 - 10:31:41
Dernière modification le : lundi 26 mars 2018 - 16:34:05
Document(s) archivé(s) le : dimanche 10 juin 2018 - 13:29:01

Fichiers

snap.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Olivier Devillers, Sylvain Lazard, William Lenhart. 3D Snap Rounding. SoCG 2018 - 34th International Symposium on Computational Geometry , Jun 2018, Budapest, Hungary. pp.30:1 - 30:14, 〈10.4230/LIPIcs.SoCG.2018.30〉. 〈hal-01727375〉

Partager

Métriques

Consultations de la notice

189

Téléchargements de fichiers

64