Exactly. But I think you can get O(n) by using the linear time K- median selection algorithm (see for example http://en.wikipedia.org/wiki/Selection_algorithm) on the distances to the target point.
These kinds of questions where you process all n points every time are seldom of practical interest. What is usually wanted is to build a query data structure once in O(n), O(n log n) or even O(n^2) time and then handle repeated queries and individual updates in O(log n) or O(1) time. The classic example is a kd-tree. On Nov 22, 2:31 pm, Dave <[email protected]> wrote: > @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 <[email protected]> wrote: > > > > > On Tue, Nov 22, 2011 at 8:43 PM, Dave <[email protected]> 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 <[email protected]> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
