Processing math: 100%
Round­ing meshes in 3D
Syl­vain Lazard

Let P be a set of n poly­gons in 3D each of con­stant com­plex­ity and with pair­wise dis­joint in­te­ri­ors. We pro­pose a round­ing al­go­rithm that maps P to a sim­pli­cial com­plex Q whose ver­tices have in­te­ger co­or­di­nates. Every face of P is mapped to a set of faces (or edges or ver­tices) of Q and the map­ping from P to Q can be done through a con­tin­u­ous mo­tion of the faces such that (i) the L_\infty Haus­dorff dis­tance be­tween a face and its image dur­ing the mo­tion is at most 3/2 and (ii) if two points be­come equal dur­ing the mo­tion, they re­main equal through the rest of the mo­tion. In the worst case, the size of Q is O(n^{13}) and the time com­plex­ity of the al­go­rithm is O(n^{15}) but these com­plex­i­ties are likely not tight and we ex­pect, in prac­tice on non-patho­log­i­cal data, O(n^{3/2}) space and time com­plex­i­ties.