conference paper
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
SCG: Symposium on Computational Geometry
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 shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the 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 shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm.
ACM2011Paris, France
eng
Proceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998225
187 - 196
https://research-explorer.app.ist.ac.at/record/3115
Berberich, Eric, et al. “Deconstructing Approximate Offsets.” <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry</i>, ACM, 2011, pp. 187–96, doi:<a href="https://doi.org/10.1145/1998196.1998225">10.1145/1998196.1998225</a>.
Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing Approximate Offsets.” In <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry</i>, 187–96. ACM, 2011. <a href="https://doi.org/10.1145/1998196.1998225">https://doi.org/10.1145/1998196.1998225</a>.
E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp. 187–196.
E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing approximate offsets,” in <i>Proceedings of the twenty-seventh annual symposium on Computational geometry</i>, Paris, France, 2011, pp. 187–196.
Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry. SCG: Symposium on Computational Geometry 187–196.
Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate offsets. In: <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry</i>. ACM; 2011:187-196. doi:<a href="https://doi.org/10.1145/1998196.1998225">10.1145/1998196.1998225</a>
Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2011). Deconstructing approximate offsets. In <i>Proceedings of the twenty-seventh annual symposium on Computational geometry</i> (pp. 187–196). Paris, France: ACM. <a href="https://doi.org/10.1145/1998196.1998225">https://doi.org/10.1145/1998196.1998225</a>
33292018-12-11T12:02:42Z2020-01-21T11:49:01Z