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.