---
_id: '3115'
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 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.'
acknowledgement: "We thank Eyal Flato (Plataine Ltd.) for raising the offset-deconstruction
  problem in connection with wood cutting. We also thank Tim Bretl (UIUC) for suggesting
  the digital-pen offset-deconstruction problem. This work has been supported in part
  by the Israel Science Foundation (grant no. 1102/11), by the German–Israeli Foundation
  (grant no. 969/07), by the Hermann Minkowski–Minerva Center for Geometry at Tel
  Aviv University, and by the EU Project under Contract No. 255827 (CGL—Computational
  Geometry Learning).\r\n"
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. <i>Discrete &#38; Computational Geometry</i>. 2012;48(4):964-989. doi:<a
    href="https://doi.org/10.1007/s00454-012-9441-5">10.1007/s00454-012-9441-5</a>
  apa: Berberich, E., Halperin, D., Kerber, M., &#38; Pogalnikova, R. (2012). Deconstructing
    approximate offsets. <i>Discrete &#38; Computational Geometry</i>. Springer. <a
    href="https://doi.org/10.1007/s00454-012-9441-5">https://doi.org/10.1007/s00454-012-9441-5</a>
  chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing
    Approximate Offsets.” <i>Discrete &#38; Computational Geometry</i>. Springer,
    2012. <a href="https://doi.org/10.1007/s00454-012-9441-5">https://doi.org/10.1007/s00454-012-9441-5</a>.
  ieee: E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing
    approximate offsets,” <i>Discrete &#38; Computational Geometry</i>, vol. 48, no.
    4. Springer, pp. 964–989, 2012.
  ista: Berberich E, Halperin D, Kerber M, Pogalnikova R. 2012. Deconstructing approximate
    offsets. Discrete &#38; Computational Geometry. 48(4), 964–989.
  mla: Berberich, Eric, et al. “Deconstructing Approximate Offsets.” <i>Discrete &#38;
    Computational Geometry</i>, vol. 48, no. 4, Springer, 2012, pp. 964–89, doi:<a
    href="https://doi.org/10.1007/s00454-012-9441-5">10.1007/s00454-012-9441-5</a>.
  short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, Discrete &#38; Computational
    Geometry 48 (2012) 964–989.
corr_author: '1'
date_created: 2018-12-11T12:01:28Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2025-09-30T08:01:36Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-012-9441-5
external_id:
  arxiv:
  - '1109.2158'
  isi:
  - '000311503200006'
intvolume: '        48'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1109.2158
month: '12'
oa: 1
oa_version: Preprint
page: 964 - 989
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3584'
quality_controlled: '1'
related_material:
  record:
  - id: '3329'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Deconstructing approximate offsets
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 48
year: '2012'
...