
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
February 9th, 2008, 03:51 PM  #1 
Joined: Feb 2008 Posts: 1  Finding clusters of points on a grid
I need to find clusters of points on a grid 2000.00*2000.00 (2 d.p. accuracy). Specifically, i need to find the cluster which has the most points in the smallest area. The number of points is arbitrary, and the algorithm needs to be as fast as possible. Please help.

My Computer Forum is free to register and we welcome everyone! 
February 9th, 2008, 07:53 PM  #2 
Joined: Dec 2007 Posts: 138  Re: Finding clusters of points on a grid
# of points is arbitrary, and pseudorandom? Isn't that problem NPComplete? 
February 10th, 2008, 05:09 PM  #3 
Joined: Dec 2007 Posts: 232  Re: Finding clusters of points on a grid
We need to know more. To solve the problem at all (regardless of efficiency) we need to know what "the most points in the smallest area" means. If you can choose any area you want, it would be just large enough to fit a single point, right? Otherwise you must have limitations on the size and shape of the area, and we need to know this. Second, if you want this to be efficient: * Are approximate answers acceptable, or not? For dense collections of points an approximate answer might be a thousand times faster. * How many points are there? If there are ten points in a 200000x200000 grid, then the optimal method will likely go pointbypoint; if you have a billion points, probably not. If this scales from 1 point to 40 billion points, then it's dense 'on average' so a dense method is probably best. 

Tags 
clusters, finding, grid, points 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
help me for finding gboxapp software  jamiulislam  Computer Science  0  January 21st, 2013 02:02 AM 
Help in finding a high performance notebook!  deanSs  Computer Hardware  2  February 9th, 2012 12:55 PM 
Finding an acyclic orientation in a graph  Anonymous Coward  Algorithms  7  January 24th, 2010 12:28 PM 
Finding large 2primes  NClement  Computational Science  13  August 7th, 2008 05:03 AM 