Capturing points with a rotating polygon (and a 3D extension) (Q2000002): Difference between revisions

Rotation of an \(n\)-vertex simple polygon \(P\) around a fixed center to cover a maximum (or minimum) number out of \(m\) given points of the plane is shown to be 3SUM-hard. A simple sweep over all critical angles where some given point crosses an edge of \(P\) solves this problem in \(O(nm\log(nm))\) time and \(O(nm)\) space. This complexity is often improved by way of a moving radius sweep-circle maintaining its intersection with \(P\). This latter idea is then adapted to the extended problem where the rotation center may be moved along a segment, resulting in a plane-arrangement searchable for optimal depth, all of this in \(O(n^2m^2\log(nm))\) time and \(O(n^2m^2)\) space. Finally, a method of this same complexity for the 3D version with fixed rotation center is outlined.