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.
