LIPIcs.SoCG.2018.30.pdf
- Filesize: 0.76 MB
- 14 pages
Document
3D Snap Rounding
Authors
-
Part of:
Volume:
34th International Symposium on Computational Geometry (SoCG 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-08
Cite As Get BibTex
Olivier Devillers, Sylvain Lazard, and William J. Lenhart. 3D Snap Rounding. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.30
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_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}).
Subject Classification
Keywords
- Geometric algorithms
- Robustness
- Fixed-precision computations
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Mark de Berg, Dan Halperin, and Mark Overmars. An intersection-sensitive algorithm for snap rounding. Computational Geometry, 36(3):159-165, 2007. URL: http://dx.doi.org/10.1016/j.comgeo.2006.03.002.
- Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation: Two Applications of a New Geometry-based Perturbation Framework. Journal of Computational Geometry, 8(1):282-315, 2017. URL: http://dx.doi.org/10.20382/jocg.v8i1a11.
- Steven Fortune. Polyhedral modelling with multiprecision integer arithmetic. Computer-Aided Design, 29(2):123-133, 1997. Solid Modelling. URL: http://dx.doi.org/10.1016/S0010-4485(96)00041-3.
- Steven Fortune. Vertex-rounding a three-dimensional polyhedral subdivision. Discrete &Computational Geometry, 22(4):593-618, 1999. URL: http://dx.doi.org/10.1007/PL00009480.
- Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, and Paul J. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proceedings of the thirteenth annual symposium on Computational geometry, pages 284-293. ACM, 1997. URL: http://dx.doi.org/10.1145/262839.262985.
- Daniel H. Greene and F. Frances Yao. Finite-resolution computational geometry. In Foundations of Computer Science, 1986., 27th Annual Symposium on, pages 143-152. IEEE, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.19.
- Leonidas J. Guibas and David H. Marimont. Rounding arrangements dynamically. International Journal of Computational Geometry &Applications, 8(02):157-178, 1998. URL: http://dx.doi.org/10.1142/S0218195998000096.
- Dan Halperin and Eli Packer. Iterated snap rounding. Computational Geometry, 23(2):209-225, 2002. URL: http://dx.doi.org/10.1016/S0925-7721(01)00064-5.
- John Hershberger. Improved output-sensitive snap rounding. Discrete & Computational Geometry, 39(1):298-318, Mar 2008. URL: http://dx.doi.org/10.1007/s00454-007-9015-0.
- John Hershberger. Stable snap rounding. Computational Geometry, 46(4):403-416, 2013. URL: http://dx.doi.org/10.1016/j.comgeo.2012.02.011.
- John D. Hobby. Practical segment intersection with finite precision output. Computational Geometry, 13(4):199-214, 1999. URL: http://dx.doi.org/10.1016/S0925-7721(99)00021-8.
-
V. Milenkovic and L. R. Nackman. Finding compact coordinate representations for polygons and polyhedra. IBM Journal of Research and Development, 34(35):753-769, 1990.
-
Victor Milenkovic. Rounding face lattices in d dimensions. In Proceedings of the 2nd Canadian Conference on Computational geometry, pages 40-45, 1990.
- Eli Packer. Iterated snap rounding with bounded drift. Computational Geometry, 40(3):231-251, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2007.09.002.