Rounding meshes in 3D
Sylvain Lazard

Let $P$ be a set of $n$ polygons in 3D each of constant complexity and with pairwise disjoint interiors. We propose a rounding algorithm that maps $P$ to a simplicial complex $Q$ whose vertices have integer coordinates. Every face of $P$ is mapped to a set of faces (or edges or vertices) of $Q$ and the mapping from $P$ to $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 $Q$ is $O(n^{13})$ and the time complexity of the algorithm is $O(n^{15})$ but these complexities are likely not tight and we expect, in practice on non-pathological data, $O(n^{3/2})$ space and time complexities.