Deconstructing Approximate Offsets

— filed under: CGAL, paper, R2, minkowski

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₁.
Construct inner (outer) δ-approximation of the r-inset of S₁, i.e. inner (outer) 2δ-approximation of Π. Let's denote it S₂.
Notice that S₂ is a polygon, and in the inner variant S₂ ⊆ Π, therefore it can serve as a valid P, if the algoritm returns YES.
Construct inner (outer) δ-approximation of the r+ε-offset of S₂, i.e. inner (outer) 3δ-approximation of Q'. Let's denote it S₃.
If Q ⊆ S₃ 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.

Contacts

Eric Berberich
Michael Kerber
Dan Halperin
Roza Pogalnikova

Sections

Personal tools