---
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 P; then, P''s offset
constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We
give an O(nlogn)-time exact decision algorithm that handles any polygonal shape,
assuming the real-RAM model of computation. A variant of the algorithm, which
we have implemented using the cgal library, is based on rational arithmetic and
answers the same deconstruction problem up to an uncertainty parameter δ its running
time additionally depends on δ. If the input shape is found to be approximable,
this algorithm also computes an approximate solution for the problem. It also
allows us to solve parameter-optimization problems induced by the offset-deconstruction
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 P with at most
one more vertex than a vertex-minimal one.@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.1007/s00454-012-9441-5
bibo_issue: '4'
bibo_volume: 48
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Deconstructing approximate offsets@
...