My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
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.
circleBounding is offline  
 

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 pseudo-random?

Isn't that problem NP-Complete?
cknapp is offline  
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 point-by-point; 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.
CRGreathouse is offline  
Reply

  My Computer Forum > Computer Science Forum > Algorithms

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 2-primes NClement Computational Science 13 August 7th, 2008 05:03 AM





Copyright © 2018 My Computer Forum Forum. All rights reserved.