Avoid computing n distances per node in tree

[andreasnoack]

It seems that one of the main reasons for constructing the KDTree is to have a more efficient way of computing distances but right no all n distances are computed for each node, see

Loess.jl/src/Loess.jl

Lines 81 to 84 in 9127229

	# distance to each point
	for i in 1:n
	ds[i] = euclidean(vec(vert), vec(xs[i,:]))
	end

. I believe it should be possible to use the tree to make of these calculations O(log(n)) instead of O(n).

[dcjones]

I think the neighborhood size q = ceil(Int, (span * n)) is typically such that this brute force approach is fine.

The brute force approach is O(kn) where k is the number of vertices. We could probably use the kd-tree to lookup for each point which vertices' neighborhoods it resides in. But I think points will be in an average of span*k neighborhoods (where span=0.75 by default). This will end up being something like O(n*(log(k) + span*k)) = O(kn), so it's not an asymptotic improvement as long as neighborhoods are defined proportionally like this. If span is small, it might be practically more efficient though.

[andreasnoack]

This is actually mentioned briefly in the original paper. The purpose of KD-tree is not to help with the nearest neighbor calculation. Maybe it's possible to improve here but I don't think my original thinking here is correct so I'll close.