Computing the Minkowski Sum of Monotone Polygons

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents algorithms for computing the Minkowski sum of two polygons P and Q for a family of problems. For P being convex and Q being monotone, an algorithm is given with O(nm) time and space complexity. For both P and Q being monotone polygons, an O(nm log nm) time algorithm is presented and it is shown that the complexity of the sum is ⊖(nmα(min(n,m))) in the worst case, where α(・) is the inverse of Ackermann's function. Finally, an O((nm+k)log nm) time complexity algorithm is given when P is monotone and Q is simple, where k in the worst case could be ⊖(n^2m). The complexity of P ⊕ Q is shown to be ⊖(n^2m) in the worst case. Here, m and n denote the number of edges of P and Q, respectively.

• 社団法人電子情報通信学会の論文
• 1997-02-25

著者

• Hernandez-barrera Antonio

  Department Of Mathematics Faculty Of Science Hiroshima University

関連論文

• Computing the Minkowski Sum of Monotone Polygons

スポンサーリンク