I am looking for a data structure that supports (efficient) nearest neighbor search in 3d-space with special cases for “near”.

Given:

• P – the set of points in 3d space
• s – A point not in P to find the closest points to from `P
• k – the number of points that can be used for closeness calculation (see below)
• f_k: p_i -> d – a function f_k that maps k points p_i to a distance d

Find:

• A subset S = {s_i} of P of size k such that f_k(s_i) is minimum

So basically for k=1 I need regular euclidean distance to the search point but for two or more points the function f can get more complicated – in my use case I can combine the points together to yield a new point not in the set P. (Think vector addition for a simple f function but it can be more complicated than that.)

Since |P| = 3000 and k can easily be 3 I cannot just store all possible results of f_k for all points in P – I can calculate it when indexing the data structure, though.

For k=1 I was just using k-D trees for now, but I am looking for a data structure that supports on the fly distance calculation from multiple points – is there such a thing?

I would need an implementation in C++ in the end but that’s not so important.