Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Rounding meshes in 3D

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^{13})$ and the time complexity of the algorithm is $O(n^{15})$ but, under reasonable assumptions, these complexities decrease to $O(n^{4}\sqrt{n})$ and $O(n^{5})$. Furthermore, these complexities are likely not tight and we expect, in practice on non-pathological data, $O(n\sqrt{n})$ space and time complexities.
Document type :
Journal articles
Complete list of metadata
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Tuesday, April 21, 2020 - 12:45:31 PM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM


Files produced by the author(s)




Olivier Devillers, Sylvain Lazard, William Lenhart. Rounding meshes in 3D. Discrete and Computational Geometry, Springer Verlag, 2020, ⟨10.1007/s00454-020-00202-2⟩. ⟨hal-02549290⟩



Record views


Files downloads