Monotone Polygon Containment Problems Under Translation

情報処理学会 被引用文献1件

この論文をさがす

説明

We investigate the problem of determining whether a polygon I can be translated to fit inside another polygon E without constructing the whole feasible region. For rectilinearly 2-concave polygons an ョﾈm+n+klog^2mn) algorithm is presented in which m is the number of edges of I n is the number of edges of E and k is the number of sliding steps. In the worst case k may be proportional to ョﾈmn). Since the feasible region may have O(m^2n^2)edges this algorithm runs more efficiently than one for finding the whole feasible region. An O(m + n + k log m + t) algorithm is also presented for monotone polygons. In the worst case t may be proportional to O(mnヰﾈmn) log m) where a( . ) is the inverse of Ackermann's function.

We investigate the problem of determining whether a polygon I can be translated to fit inside another polygon E without constructing the whole feasible region. For rectilinearly 2-concave polygons, an ョﾈm+n+klog^2mn) algorithm is presented in which m is the number of edges of I, n is the number of edges of E, and k is the number of sliding steps. In the worst case, k may be proportional to ョﾈmn). Since the feasible region may have O(m^2n^2)edges, this algorithm runs more efficiently than one for finding the whole feasible region. An O(m + n + k log m + t) algorithm is also presented for monotone polygons. In the worst case, t may be proportional to O(mnヰﾈmn) log m), where a( . ) is the inverse of Ackermann's function.

収録刊行物

被引用文献 (1)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ