---
res:
bibo_abstract:
- 'We consider the offset-deconstruction problem: 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 P with a disk of fixed radius? If
it does, we also seek a preferably simple-looking solution shape P; then, P''s
offset constitutes an accurate, vertex-reduced, and smoothened approximation of
Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal
shape, assuming the real-RAM model of computation. An alternative algorithm, based
purely on rational arithmetic, answers the same deconstruction problem, up to
an uncertainty parameter, and its running time depends on the parameter δ (in
addition to the other input parameters: n, δ and the radius of the disk). If the
input shape is found to be approximable, the rational-arithmetic algorithm also
computes an approximate solution shape for the problem. For convex shapes, the
complexity of the exact decision algorithm 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. Our study is motivated by applications from two different domains. However,
since the offset operation has numerous uses, we anticipate that the reverse question
that we study here will be still more broadly applicable. We present results obtained
with our implementation of the rational-arithmetic algorithm.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Eric
foaf_name: Berberich, Eric
foaf_surname: Berberich
- foaf_Person:
foaf_givenName: Dan
foaf_name: Halperin, Dan
foaf_surname: Halperin
- foaf_Person:
foaf_givenName: Michael
foaf_name: Kerber, Michael
foaf_surname: Kerber
foaf_workInfoHomepage: http://www.librecat.org/personId=36E4574A-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8030-9299
- foaf_Person:
foaf_givenName: Roza
foaf_name: Pogalnikova, Roza
foaf_surname: Pogalnikova
bibo_doi: 10.1145/1998196.1998225
dct_date: 2011^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: Deconstructing approximate offsets@
...