use a max heap of size k, On Tue, Nov 22, 2011 at 11:38 PM, Aamir Khan <ak4u2...@gmail.com> wrote:
> > On Tue, Nov 22, 2011 at 8:43 PM, Dave <dave_and_da...@juno.com> wrote: > >> @Ganesha: You could use a max-heap of size k in time O(n log k), which >> is less than O(n log n) if k < O(n). > > > We can always ensure that k <= n/2. > > If k >= n/2 then the problem can be stated as, find m points farthest from > the given point by creating min-heap of size m. The elements which were > present in input but not in heap will be the points nearest to the given > point, where m = n-k. > > > > >> Dave >> >> On Nov 22, 8:56 am, ganesha <suresh.iyenga...@gmail.com> wrote: >> > Given a set of points in 2D space, how to find the k closest points >> > for a given point, in time better than nlgn. >> >> > > -- > Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee > > > -- > 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. > -- * Regards* *"The Coder"* *"Life is a Game. The more u play, the more u win, the more u win , the more successfully u play"* -- 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.
