What is the definition of "closest to each other"? Do you mean that the distance from the selected point to the most distant of the three is minimized? Or that the smallest circle enclosing the points is minimized? Or that the total distance between all pairs of points is the smallest? Or that the total distance from the selected points to the three other points is the smallest?
In any case, I think that binning is a good place to start. If you have N points in a region of area A, you can prove that if you divide up the region into (N/3)-1 regions, at least one of those regions will contain 4 points. Divide up the region containing the points into a grid of at least that many square regions and make a list of points which fall in each region. If one of these areas contains a large number of points (You'll have to experiment to determine what this number should be. Probably somewhere between 200 and 1000.) you can repeat the binning process on just that area. Then process these binned regions by considering each point as a potential selected point. Compute the distance to the other points in the region and the adjacent regions, keeping track of the three closest. When you are done, if the point is better than the best you have found so far, store it as the best so far. The time complexity for each region is O(P^2) where P is the number of points in the region. If you have R regions, the total runtime is O(R*(N/R)^2) = O(N^2/R). But since R=(N/3)-1 the runtime complexity is O(N). Don On May 2, 12:49 pm, Nishant Pandey <nishant.bits.me...@gmail.com> wrote: > Guys i am looking for optimize algorithm for this, please help. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
