Berberich, Eric
Eric
Berberich
Halperin, Dan
Dan
Halperin
Kerber, Michael
Michael
Kerber0000-0002-8030-9299
Pogalnikova, Roza
Roza
Pogalnikova
Polygonal reconstruction from approximate offsets
TU Dortmund
2010
2018-12-11T12:05:30Z
2019-08-02T12:38:18Z
conference
/record/3850
/record/3850.json
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 with a disk of fixed radius? If it does, we also seek a preferably simple solution shape P;P’s offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give a decision algorithm for fixed radius in O(nlogn) time that handles any polygonal shape. For convex shapes, the complexity 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.