From:           shebs@utah-cs.UUCP (Stanley Shebs)
Newsgroups:     comp.theory
Subject:        Clustering to Minimize Window Motion
Keywords:       algorithms, clustering, computational geometry
Date:           21 Aug 87 16:27:47 GMT
Organization:   PASS Research Group

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

(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!)