Optimal polygon placement

Given a simple polygon P with m vertices and a set S of n points in the plane, we consider the problem of finding a rigid motion placement of P that contains the maximum number of points in S. We present two solutions to this problem that represent time versus space tradeoffs. The first algorithm runs in O(n3m3) expected time using O(n2m2) space. The second algorithm runs in O(n3m3 log(nm)) deterministic time and O(nm) space. While these algorithms represent a substantial improvement in the time bounds of previous work the main contribution is that the approach is extendible to related rigid motion placement problems including polygonal annulus placement.