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
@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 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.
--
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
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
@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
