🚀 go-pugleaf

From: Stanley Shebs <shebs@cs.utah.edu>
Subject:      Clustering to Minimize Window Motion

Does anybody know of any good algorithms to cluster nearby points to
minimize the moving of a window over those points?  In case that wasn't
clear, suppose I have a set of points randomly scattered over the plane,
and a rectangular window of some fixed size, and I want to get each point
visible inside the window at least once.  I move the window some number of
times, and that number will of course be between 0 (if all the points fit in
one view) and the number of points (if they're all far apart).  Moving the
window is expensive, so what I want is an algorithm to determine the smallest
set of window positions that covers all the points.  The algorithm should
probably be quadratic in the number of points or better - optimality is
less important.  Algorithms, references and reductions to similar problems
are all welcome...
     
                            stan shebs
                            shebs@cs.utah.edu
     
(Incidentally, this problem arose in connection with my recently posted
game "xconq", where the points are playing pieces and the window is an
X window, so a good algorithm will likely show up in the next release!)