1. Rounding Meshes in 3D.
- Author
-
Devillers, Olivier, Lazard, Sylvain, and Lenhart, William J.
- Subjects
- *
POLYGONS , *SOLID geometry , *MOTION , *INTEGERS - Abstract
Let P be a set of n polygons in R 3 , 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 ∞ 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, under reasonable assumptions, these complexities decrease to O (n 4 n) and O (n 5) . Furthermore, these complexities are likely not tight and we expect, in practice on non-pathological data, O (n n) space and time complexities. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF