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 metadatas


https://hal.inria.fr/hal-01727375
Contributor : Olivier Devillers <>
Submitted on : Friday, March 9, 2018 - 10:31:41 AM
Last modification on : Wednesday, July 31, 2019 - 2:51:31 PM
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

281

Files downloads

240