Deconstructing Approximate Offsets

Talk announcement
HIIT Seminar Kumpula, Friday September 9 10:15, Exactum B222

SPEAKER:
Eric Berberich
Max-Planck-Institut Informatik MPII

TITLE:
Deconstructing Approximate Offsets

ABSTRACT:
Today's problem arised in a wood-cutting company that got
a new cutter. The new tools needs a smaller safety-margin
to the desired cutout. However, the only available legacy
data for the old cutter is an approximated offset, that is,
it is desired to regain the original shape before
offsetting.

Formally we study the following problem:
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 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. The talk also discusses
recent achievements as to use only rational arithmetic
for the decision and the search of good parameters
eps and r.