How to quickly find k nearest points to a plane in 3 or more dimensions

Question

I need to quickly find the k nearest points to a plane (or hyperplane) in 3 (or more) dimensions. Is there a fast way to perform this search, using some sort of clever data structure (similar to how a kd-tree works for k nearest neighbors)?

I know I can rotate the plane and all the points so that the plane is orthogonal to one of the axes, then measure the distance of each point to the plane by simply using the ordinate in that axis. However, the time complexity of this brute force approach is O(N), where (N) is the number of points. Since I have to find the k nearest neighbors for a large number of planes and a large number of points, I need to find a faster algorithm if possible.

Answer 1

measure the distance by using dot product with hyper plane normal... So let:

n - be the hyperplane normal unit vector
p0 - be any point point on the hyperplane
p[i] - be i-th point from your pointcloud i={ 0,1,2...n-1 }

then the distance to hyperplane plane is:

d = |dot( p[i] - p0 , n )|

as you can see no need to transform/align anything and its O(1) without any expensive operations. I expect that any pre sorting of points or using clever structures will be slower than this in most cases...

Now you got 2 options either compute the d for each point and then quick sort which leads to O(n.log(n)) time and O(n) space complexity.

Or remember k closest points on the run leading to O(k*n) time and O(k) space.

So if k is small (k < log(n)) or you have not enough memory to spare use second approach otherwise use first one ...

Answer 2

I think you can simply use any spatial data structure (kd-tree, R-tree, ...) that supports custom distance functions. You should be able to define a distance function that simply uses the distance to the plane instead of distance to a center point.

How to calculate this distance is described by @Spektre.

I have no idea how that scales, because it may depend on the kNN search algorithm used by the implementation. However, I believe the standard algorithm (Hjaltason and Samet: "Distance browsing in spatial databases.") should at least be better than O(n).

In case you are using Java, the R-Tree, Quadtree and PH-Tree indexes in my TinSpin library all use this algorithm.