Optimal placement of convex polygons to maximize point containment
Matthew T. Dickerson, Daniel Scharstein · Symposium on Discrete Algorithms · 1996
Given a convex polygon P with m vertices and a set S of n points in the plane, we consider the problem of finding a placement of P (allowing both translation and rotation) that contains the maximum number of points in S. We present first an algorithm requiring O(n^2km^2log(mn)) time and O(n + m) space, where k is the maximum number of points contained. We then give a refinement that makes use of bucketing to improve the running time to O(nk^2c^2m^2log(mk)), where c is the ratio of length to width of the polygon. This provides an improvement over the best previously known algorithm linear in n when k is large (@Q(n)) and a cubic when k is small. We also show that the algorithm can be extended to solve bichromatic and general weighted variants of the problem. The algorithm is self-contained and utilizes the geometric properties of the containing regions in the parameter space of transformations.