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.