Skip to Main content Skip to Navigation
Conference papers

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})$.
Document type :
Conference papers
Complete list of metadata


https://hal.inria.fr/hal-01727375
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, March 9, 2018 - 10:31:41 AM
Last modification on : Wednesday, November 3, 2021 - 7:56:52 AM
Long-term archiving on: : Sunday, June 10, 2018 - 1:29:01 PM

Files

snap.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

393

Files downloads

412