@all.. To decide which points are within the range R, we need to look a each point..Hence the lower bound would be O(N)..
Now, for doing it in < O(N) we need to have the input being given in a particular order, basically the datastructure which stores the graph projects some releationship b/w all the points.. @utkarsh.. Say, the graph is represented as an adjancency matrix or list with edges showing the connection and weights defined the distance b/w the points...and assuming that this datastructure is given to u.. then its as good as applying dijikstra's to find the shortest path from A to all other vertices... and check which shortest paths are smaller than R... Basically it all depends on how the data is being represented.. @dabbcomputer Correct me if i m wrong.. On Jan 6, 11:48 am, shady <[email protected]> wrote: > how will one come to know which points are cut-out from the circle ? > i fail to understand how can it be less than O(n) unless you store the > given N points in a data structure ... where preprocessing itself involves > O(N)... -- 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.
