Sweeping Minimum Perimeter Enclosing Parallelograms: Optimal Crumb Cleanup
Mary Leah Karker · Canadian Conference on Computational Geometry · 2010
We examine the problem of pushing all the points of a planar region into one point using parallel sweeps of an innite line, minimizing the sum of the lengths of the sweep vectors. We characterize the optimal 2-sweeps of triangles, and provide a linear-time algorithm for convex polygons.