Monotone Polygon Containment Problems Under Translation

IPSJ 1 Citations

Search this article

Description

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.

Journal

Citations (1)*help

See more

Details 詳細情報について

Report a problem

Back to top