Personal tools
You are here: Home Projects Internal Projects Deconstructing Approximate Offsets
« March 2017 »
Log in

Forgot your password?

Deconstructing Approximate Offsets

— filed under: , , ,

    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.


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

Generic 2
Parallel 2 Intersect 2

(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?
  1. Construct Qε = Offset(Q, ε).
  2. Construct Π = Inset(Qε, r). (Π is not generally a polygon, therefore it cannot serve as P in question, but it has to contain it).
  3. Construct Q' = Offset(Π, r+ε).
  4. If Q ⊆ Q' then YES otherwise NO.

The Rational Arithmetic Algorithm Inner (and Outer) variant

  1. Construct inner (outer) δ-approximation of Qε. Let's denote it S1.
  2. 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.
  3. Construct inner (outer) δ-approximation of the  r+ε-offset of S2, i.e. inner (outer) 3δ-approximation of Q'. Let's denote it S3.
  4. If Q ⊆ S3 then YES (UNDECIDED) otherwise UNDECIDED (NO).


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:


wheel y wheel n wheel u wheel un
(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.




Eric Berberich
null null
Michael Kerber
null null
Dan Halperin
Roza Pogalnikova



Document Actions