DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2018.30

3D Snap Rounding

Authors: Olivier Devillers, Sylvain Lazard, and William J. Lenhart

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

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}).

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{devillers_et_al:LIPIcs.SoCG.2018.30,
  author =	{Devillers, Olivier and Lazard, Sylvain and Lenhart, William J.},
  title =	{{3D Snap Rounding}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.30},
  URN =		{urn:nbn:de:0030-drops-87438},
  doi =		{10.4230/LIPIcs.SoCG.2018.30},
  annote =	{Keywords: Geometric algorithms, Robustness, Fixed-precision computations}
}

Search Results

Documents authored by Lenhart, William J.

3D Snap Rounding

Abstract

Cite as

Thanks for your feedback!

Could not send message