---
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@
...