the reason i asked you about problem link is because the solution to your problem depends on the way you want to use it...
1. if each time there are new N points and radius R, and only one query for it...then it just can't be O(n) 2. if N points are fixed and there are like 10000+ queries then you can store it in some dataset and retrieve the result for that in O(logn) On Fri, Jan 6, 2012 at 12:29 PM, amrit harry <[email protected]>wrote: > i also think so.... data must be represent in some special form.... i > heard about K-D trees but not yet studied about it.... > > > On Fri, Jan 6, 2012 at 12:26 PM, Lucifer <[email protected]> wrote: > >> @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. >> >> > > > -- > AMRIT > > > -- > 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. > -- 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.
