Exact and approximate construction of offset polygons

The Minkowski sum of two sets A,B∈R2A,B∈R2, denoted A⊕BA⊕B, is defined as {a+b∣a∈A,b∈B}{a+b∣a∈A,b∈B}. We describe an efficient and robust implementation of the construction of the Minkowski sum of a polygon in R2R2 with a disc, an operation known as offsetting the polygon. Our software package includes a procedure for computing the exact offset of a straight-edge polygon, based on the arrangement of conic arcs computed using exact algebraic number-types. We also present a conservative approximation algorithm for offset computation that uses only rational arithmetic and decreases the running times by an order of magnitude in some cases, while having a guarantee on the quality of the result. The package will be included in the next public release of the Computational Geometry Algorithms Library, Cgal Version 3.3. It also integrates well with other Cgal packages; in particular, it is possible to perform regularized Boolean set-operations on the polygons the offset procedures generate.