Skip to Main content Skip to Navigation

3D Snap Rounding

Olivier Devillers 1 Sylvain Lazard 1 William Lenhart 2
1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
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 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})$.
Document type :
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, February 1, 2018 - 5:39:05 PM
Last modification on : Saturday, October 16, 2021 - 11:26:10 AM
Long-term archiving on: : Friday, May 25, 2018 - 4:37:18 PM


Files produced by the author(s)


  • HAL Id : hal-01698928, version 1


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



Record views


Files downloads