---
_id: '3329'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Eric
  full_name: Berberich, Eric
  last_name: Berberich
- first_name: Dan
  full_name: Halperin, Dan
  last_name: Halperin
- first_name: Michael
  full_name: Kerber, Michael
  id: 36E4574A-F248-11E8-B48F-1D18A9856A87
  last_name: Kerber
  orcid: 0000-0002-8030-9299
- first_name: Roza
  full_name: Pogalnikova, Roza
  last_name: Pogalnikova
citation:
  ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate
    offsets. In: <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational
    Geometry</i>. ACM; 2011:187-196. doi:<a href="https://doi.org/10.1145/1998196.1998225">10.1145/1998196.1998225</a>'
  apa: 'Berberich, E., Halperin, D., Kerber, M., &#38; Pogalnikova, R. (2011). Deconstructing
    approximate offsets. In <i>Proceedings of the twenty-seventh annual symposium
    on Computational geometry</i> (pp. 187–196). Paris, France: ACM. <a href="https://doi.org/10.1145/1998196.1998225">https://doi.org/10.1145/1998196.1998225</a>'
  chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing
    Approximate Offsets.” In <i>Proceedings of the Twenty-Seventh Annual Symposium
    on Computational Geometry</i>, 187–96. ACM, 2011. <a href="https://doi.org/10.1145/1998196.1998225">https://doi.org/10.1145/1998196.1998225</a>.
  ieee: E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing
    approximate offsets,” in <i>Proceedings of the twenty-seventh annual symposium
    on Computational geometry</i>, Paris, France, 2011, pp. 187–196.
  ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate
    offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry.
    SCG: Symposium on Computational Geometry, 187–196.'
  mla: Berberich, Eric, et al. “Deconstructing Approximate Offsets.” <i>Proceedings
    of the Twenty-Seventh Annual Symposium on Computational Geometry</i>, ACM, 2011,
    pp. 187–96, doi:<a href="https://doi.org/10.1145/1998196.1998225">10.1145/1998196.1998225</a>.
  short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of
    the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp.
    187–196.
conference:
  end_date: 2011-06-15
  location: Paris, France
  name: 'SCG: Symposium on Computational Geometry'
  start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2025-09-30T08:01:35Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998225
external_id:
  arxiv:
  - '1109.2158'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1109.2158
month: '06'
oa: 1
oa_version: Preprint
page: 187 - 196
publication: Proceedings of the twenty-seventh annual symposium on Computational geometry
publication_status: published
publisher: ACM
publist_id: '3306'
quality_controlled: '1'
related_material:
  record:
  - id: '3115'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Deconstructing approximate offsets
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...