Monotone Polygon Containment Problems Under Translation

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.