### Re: Maximum disc containing no more than k points

by **Andrew_M** » Fri, 18 Feb 2011 07:45:30 GMT

n Feb 17, 5:41m, Nitzan Shaked < XXXX@XXXXX.COM > wrote:

I told you about rather simple and probably efficient method. Assume

you have an input list of points {Xk, Yk}. Add to each member of this

list its number, so the input list will be the next: {Xk, Yk, k} where

k=0,1,...N. Make two copies of this list. Using quick sort algorithm

order the first list accordingly to X coordinate, the second one

accordingly to Y one. After this op the first list will be something

like this: {Xi, Yi, Ki} and Xi-1 <=Xi<=Xi+1 (hope, you understand,

that plus applies to index, not to coordinate). The second list will

be {Xj, Tj, Kj}. Now the third integer member of the structure

{double, double, int} after sorting points to location of an input

point number k, so you needn't waste time to look for it. Let's take a

point number k from the input array. Number i=Kk from the first list

is position of this point in the first ordered list, number j=Kk from

the list two is position of the same point in list two. Now you need

check points from the first list: i-1 and i+1, them check points from

the second list: j-1 and j+1, then from the first list: i-2, i+2, then

j-2, j+2 and so on. When to stop search? Distances fom the initial

point are not growing monotonly. On the other hand, due to the fact

that dr*dr=dx*dx+dy*dy one may be sure, that if dx=min(Xi - Xi-m, Xi+m

- Xi) it means that for all another points i+m+1, i+m+2,.. i-m-1, i-

m-2... dr will be greater then dx. Same situation with dy. Therefore,

when you find K points laying within a circle radius r with center at

point number k and after checking of the first list dx>=r check can be

stopped. This method looks rather attractive for me, simple and you

needn't to have a deal with Kd-trees and so on.