On Jan 5, 4:17 am, dabbcomputers <[email protected]> wrote: > you are given with N points on graph. and a point A on graph and range > R you have to find the points that lies within the radius of R from > point A. with complexity less than O(N).
Why does it have to be done with less complexity than O(N) ? O(N) certainly doesn't mean it will run faster. You "appear" to know more about the problem than you have stated??? You're not going to get good answers to your question unless you give more information on your problem and what your goals are. Finding an O(N) algorithm doesn't mean much in the real world unless it results in a faster running and/or more memory efficient algorithm. Based on the info you've given so far.... you need to check every single point. "O(N) or not" is irrelevant. Is there some order to your points that will allow you to trivially discard them from needing to be checked? Does your graph structure tell you anything about the location of your points in 2D or 3D space (other than, that they may be interconnected )? Do you have more than a hundred thousand points? Do you need to perform this checking operation often (in a loop) or only once? If you don't have that many points... the simplest and arguably the best algorithm is the one that has the simplest and easiest to understand coding by an average programmer. These are just my thoughts for whatever they're worth, Dan :-) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
