@shady the N is same we just have to query the data again and again.... On Fri, Jan 6, 2012 at 12:47 PM, shady <sinv...@gmail.com> wrote:
> 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 <dabbcomput...@gmail.com>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 <sourabhd2...@gmail.com> 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 <sinv...@gmail.com> 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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
