2026-07-22T03:56:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8743 2024-03-06T10:42:33Z ddc:004 open_access

3D Snap Rounding Devillers, Olivier Lazard, Sylvain Lenhart, William J. Geometric algorithms Robustness Fixed-precision computations 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_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^{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}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivier Devillers and Sylvain Lazard and William J. Lenhart 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.30 urn:nbn:de:0030-drops-87438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.30 eng https://creativecommons.org/licenses/by/3.0/legalcode