Approximate Unions of Lines and Minkowski Sums

We study the complexity of and algorithms to construct approximations of the union of lines, and of the Minkowski sum of two simple polygons. We also study thick unions of lines and Minkowski sums, which are inflated with a small disc. Let b=D/ε be the ratio of the diameter of the region of interest and the distance (or error) of the approximation. We present upper and lower bounds on the combinatorial complexity of approximate and thick unions of lines and Minkowski sums, with bounds expressed in b and the input size n. We also give efficient algorithms for the computation.