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 S1.
- Construct inner (outer) δ-approximation of the r-inset of S1, i.e. inner (outer) 2δ-approximation of Π. Let's denote it S2.
Notice that S2 is a polygon, and in the inner variant S2 ⊆ Π, therefore it can serve as a valid P, if the algoritm returns YES. - Construct inner (outer) δ-approximation of the r+ε-offset of S2, i.e. inner (outer) 3δ-approximation of Q'. Let's denote it S3.
- If Q ⊆ S3 then YES (UNDECIDED) otherwise UNDECIDED (NO).
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
Eric Berberich |
![]() |
![]() |
Michael Kerber |
![]() |
![]() |
Dan Halperin | ![]() |
![]() |
Roza Pogalnikova |
![]() |