Polygonal Reconstruction from Approximate Offsets

Can a polygonal shape Q with n vertices be expressed, up to a tolerance eps 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 solution shape P;
its offset constitutes an accurate, vertex-reduced and
smoothened approximation of Q. We give a decision
algorithm for fixed radius in O(n log^2 n) time that
handles any (bounded or unbounded, connected or
disconnected) polygonal shape.
For convex shapes, the complexity drops to O(n), and within
the same bound, we compute a solution shape P with at
most one more vertex than a vertex-minimal one.