🚀 go-pugleaf

hunter@george.ee.washington.edu (William Hunter Hudson) writes:

> Is there a better way to find the nearest 2 neighbors in LEDA
> than using 2 calls to S.nearest_neighbor?  Example:
> 
> p = point(x,y);
> // nearest:   nearest point to p
> // 2nd_nearest:   2nd nearest point to p
> 
> ps_item nearest = S.nearest_neighbor(q);       // O(n^2)
> S.change_inf(nearest, far_away);               // O(1)
> ps_item 2nd_nearest = S.nearest_neighbor(q);   // O(n^2)
> S.change_inf(nearest, back_to_original);       // O(1)


If computing distances is no too expensive -- what do you
think of: 

compute distances ;             // O(n)
sort them in descending order ; // O(n log n)
take the first 2;        	// O(1)

?
Wolf