---
_id: '3850'
abstract:
- lang: eng
  text: 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 with
    a disk of fixed radius? If it does, we also seek a preferably simple solution
    shape P;P’s offset constitutes an accurate, vertex-reduced, and smoothened approximation
    of Q. We give a decision algorithm for fixed radius in O(nlogn) time that handles
    any polygonal shape. For convex shapes, the complexity 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.
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. Polygonal reconstruction
    from approximate offsets. In: TU Dortmund; 2010:12-23.'
  apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2010). Polygonal
    reconstruction from approximate offsets (pp. 12–23). Presented at the EuroCG:
    European Workshop on Computational Geometry, Dortmund, Germany: TU Dortmund.'
  chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Polygonal
    Reconstruction from Approximate Offsets,” 12–23. TU Dortmund, 2010.
  ieee: 'E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Polygonal reconstruction
    from approximate offsets,” presented at the EuroCG: European Workshop on Computational
    Geometry, Dortmund, Germany, 2010, pp. 12–23.'
  ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2010. Polygonal reconstruction
    from approximate offsets. EuroCG: European Workshop on Computational Geometry,
    12–23.'
  mla: Berberich, Eric, et al. <i>Polygonal Reconstruction from Approximate Offsets</i>.
    TU Dortmund, 2010, pp. 12–23.
  short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, TU Dortmund, 2010,
    pp. 12–23.
conference:
  end_date: 2010-03-24
  location: Dortmund, Germany
  name: 'EuroCG: European Workshop on Computational Geometry'
  start_date: 2010-03-22
date_created: 2018-12-11T12:05:30Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:39Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 12 - 23
publication_status: published
publisher: TU Dortmund
publist_id: '2334'
quality_controlled: '1'
status: public
title: Polygonal reconstruction from approximate offsets
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2010'
...