Optimal Polygon Placement
Prosenjit K. Bose, Jason B. Morrison · 2006
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 tradeo! s. The first algorithm runs in O(n 3 m 3 ) expected time using O(n 2 m 2 ) space. The second algorithm runs in O(n 3 m 3 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.