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 interes
@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 wrote:
> On Tue, Nov 22, 2011 at 8:43 PM, Dave wrote:
> > @Ganesha: You could use a max-heap of size k in time O(n log k), wh
use a max heap of size k,
On Tue, Nov 22, 2011 at 11:38 PM, Aamir Khan wrote:
>
> On Tue, Nov 22, 2011 at 8:43 PM, Dave 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 >
On Tue, Nov 22, 2011 at 8:43 PM, Dave 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 creatin
@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).
Dave
On Nov 22, 8:56 am, ganesha 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.
--
You received this message
