Approximate unions of lines and minkowski sums |
| |
Authors: | Marc van Kreveld A Frank van der Stappen |
| |
Affiliation: | (1) Institute of Information and Computing Sciences, Utrecht University, 3508 TB Utrecht, The Netherlands |
| |
Abstract: | 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 studythick unions of lines and Minkowski sums, which are inflated with a small disc. Letb=D/ɛ be the ratio of the diameter of the region of interest and the maximum distance (or error) of the approximation. An approximate
union of lines or Minkowski sum has complexity Θ (b
2) in the worst case. The thick union ofn lines has complexity Ω(n+b
2) andO(n +b√bn), and thick Minkowski sums have complexity Ω(n
2+b2) andO((n+b)n√blogn+n
2 logn) in the worst case. We present algorithms that run inO(n+n
2/3+δ
b
4/3 andO(min(bn,n
4/3+δ
b
2/3)) time (any δ>0) for approximate and thick arrangements. For approximate Minkowski sums, the running time isO(min(b
2
n,n
2 +b
2 + (nb)4/3+δ); thick Minkowski sums takeO(n
8/3+δ
b
2/3) time to compute. |
| |
Keywords: | Minkowski sums Approximation Combinatorial complexity Algorithms |
本文献已被 SpringerLink 等数据库收录! |
|