article
Deconstructing approximate offsets
published
yes
Eric
Berberich
author
Dan
Halperin
author
Michael
Kerber
author 36E4574A-F248-11E8-B48F-1D18A9856A870000-0002-8030-9299
Roza
Pogalnikova
author
HeEd
department
We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.
Springer2012
eng
Discrete & Computational Geometry10.1007/s00454-012-9441-5
484964 - 989
https://research-explorer.app.ist.ac.at/record/3329
Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate offsets. <i>Discrete & Computational Geometry</i>. 2012;48(4):964-989. doi:<a href="https://doi.org/10.1007/s00454-012-9441-5">10.1007/s00454-012-9441-5</a>
Berberich, Eric, et al. “Deconstructing Approximate Offsets.” <i>Discrete & Computational Geometry</i>, vol. 48, no. 4, Springer, 2012, pp. 964–89, doi:<a href="https://doi.org/10.1007/s00454-012-9441-5">10.1007/s00454-012-9441-5</a>.
E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, Discrete & Computational Geometry 48 (2012) 964–989.
Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2012). Deconstructing approximate offsets. <i>Discrete & Computational Geometry</i>, <i>48</i>(4), 964–989. <a href="https://doi.org/10.1007/s00454-012-9441-5">https://doi.org/10.1007/s00454-012-9441-5</a>
Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing Approximate Offsets.” <i>Discrete & Computational Geometry</i> 48, no. 4 (2012): 964–89. <a href="https://doi.org/10.1007/s00454-012-9441-5">https://doi.org/10.1007/s00454-012-9441-5</a>.
E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing approximate offsets,” <i>Discrete & Computational Geometry</i>, vol. 48, no. 4, pp. 964–989, 2012.
Berberich E, Halperin D, Kerber M, Pogalnikova R. 2012. Deconstructing approximate offsets. Discrete & Computational Geometry. 48(4), 964–989.
31152018-12-11T12:01:28Z2019-08-02T12:38:09Z