# Deconstructing Approximate Offsets

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. We present experimental results
obtained with our implementation of the rational-arithmetic
algorithm.

**Additionally, we present a new construction of
approximate
offset polygons whose boundaries consist of straight-line
segments and circular arcs, and whose vertex coordinates
are rational. The construction time depends on the number
of vertices of the input polygonal shape and on the
approximation tolerance. **

### Illustrations

For a given *Q*, the red *P* is a candidate summand
whose exact
*r*-offset is shaded.

(a) |
(b) |
(c) |

**(a)** For a given ε,
deconstruction is ensured iff φ1 <= ε and φ2
<= ε.
Otherwise, at least one, say φ1, has to
shrink, which, however,
lets φ2
grow (and vice-versa). Difficulty:
a sharper angle lets φ2 grow faster
than φ1
decreases.

**(b)** Example where Q can be approximated by an r-offset of a P that has much fewer vertices than
Q.

**(c)** Example where Q can be approximated by the r-offset of a disconnected shape P.

### The Decision Algorithm

Is the input polygon*Q*approximable, that is

*ε-*close to the r-offset of some unspecified polygon

*P*?

- Construct
*Qε = Offset(Q, ε)*. - Construct
*Π**= Inset(**Qε**, r)*. (Π is not generally a polygon, therefore it cannot serve as*P*in question, but it has to contain it). - Construct
*Q' = Offset(**Π**, r+**ε**)*. - If
*Q ⊆ Q*' then YES otherwise NO.

### The Rational Arithmetic Algorithm Inner (and Outer) variant

- Construct inner (outer) δ-approximation of
*Qε*. Let's denote it*S*_{1}*.* - Construct inner (outer) δ-approximation of the
*r-inset*of*S*_{1}*,*i.e. inner (outer) 2δ-approximation of Π. Let's denote it*S*_{2}*.*

Notice that*S*_{2}*is a polygon, and in the inner variant**S*_{2}*⊆ Π*, therefore it can serve as a valid*P*, if the algoritm returns YES. - Construct inner (outer) δ-approximation of the
*r+**ε**-offset*of*S*_{2}*,*i.e. inner (outer) 3δ-approximation of*Q'.*Let's denote it*S*_{3}*.* - If
*Q ⊆**S*then YES (UNDECIDED) otherwise UNDECIDED (NO)._{3}

### Examples

The wheel polygon (in bold) is the input for the two-sided decision procedure, that uses inner and outer rational arithmetic variants to get a certified YES/NO unswer. The input polygon is colored with traffic lights according to the algorithm decision (green for YES, yellow for UNDECIDED, red for NO). The pictures illustrate the influence of ε and δ on the algorithm outcome:

(a) YES: ε = 1/3 r, δ = 1/36 r. |
(b) NO: ε = 1/9 r, δ = 1/36 r. |
(c) UNDECIDED: ε = 1/6 r, δ = 1/4 ε. |
(d) NO: ε = 1/6 r, δ = 1/10 ε. |

**(a)** Inner *Π* appears in green, inner *Q*' in cyan. It is easy to see that *Q ⊆ Q*', therefore *r-offset* of *P*=*Π* will be* ε-close* to *Q*.

**(b)** Outer *Π* appears in red, outer *Q*' in magenta. It is easy to see that *Q ⊆ Q*' is not true, therefore *P* with *r-offset* that is* ε-close* to *Q* does not exist.

**(c)** *Q* is not in the inner *Q'* (cyan) and is completely inside outer *Q'* (magenta). The distance between inner *Q'* and outer *Q'* <= 6δ, therefore by decreasing δ we can make it smaller and might be able to get a certified answer.

**(d)** With *δ _{d}* = 1/10 ε <

*δ*

*,*

_{c }*Q*is not completely inside outer

*Q'*(magenta), therefore is certified as not approximable.

### Links

- Eric Berberich, Dan Halperin, Michael Kerber, and Roza Pogalnikova
**Deconstructing Approximate Offsets***SoCG 2011*, 187-186, 2011 [link] [bibtex] - Eric Berberich, Dan Halperin, Michael Kerber, and Roza Pogalnikova
**Deconstructing Approximate Offsets***Discrete & Computational Geometry, December 2012, 48, Issue 4,*964-989, 2012 [link] [bibtex] - CGAL homepage: www.cgal.org
- Supplementary material: Construction of Approximate Offset

**Contacts**

**Contacts**

Eric Berberich |
||

Michael Kerber |
||

Dan Halperin | ||

Roza Pogalnikova |