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