Polygonal reconstruction from approximate offsets
Berberich, Eric
Halperin, Dan
Kerber, Michael
Pogalnikova, Roza
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.
TU Dortmund
2010
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/3850
Berberich E, Halperin D, Kerber M, Pogalnikova R. Polygonal reconstruction from approximate offsets. In: TU Dortmund; 2010:12-23.
eng
info:eu-repo/semantics/closedAccess