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/e 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.
展开▼
机译：我们研究了构建线和两个简单多边形的近似的近似的复杂性和算法。我们还研究了厚厚的工会和Minkowski Sums，它用小盘膨胀。让B = D / E是感兴趣区域的直径和近似的距离（或误差）的比率。我们在近似和厚的工会的线条和Minkowski和总和的组合复杂性上存在上限和下限，其中B和输入尺寸n表示。我们还为计算提供高效的算法。
展开▼
