From:shebs@utah-cs.UUCP (Stanley Shebs)Newsgroups:comp.theorySubject:Clustering to Minimize Window MotionKeywords:algorithms, clustering, computational geometryDate:21 Aug 87 16:27:47 GMTOrganization: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!)