@Aamir: But assuring that k <= n/2 isn't the same thing as saying that k < O(n). Note that if k = n/2, then O(n log k) = O(n log n).
Dave On Nov 22, 10:38 am, 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.
