Finding closest coordinate of a pre-known set

Question

Let's say I have a large number of conceptual objects of some kind, each of which occupies a pre-known set of points in a Cartesian 3-space.

1) What is the best combination of data structure (for modeling these objects, their occupied points, and/or the enclosing space) and algorithm for the purpose of being able to retrieve only the point within each object that lies closest to an arbitrarily selected point, with speed the first concern and memory footprint secondary (but still important)?

2) Let's say that that a point may be visually occluded with respect to another point, according to a black-box true/false rule, and I now want to retrieve the closest visible point of each object. Asking the same question as in #1, is the answer the same or is something else now advisable?

3) Let's say that the pre-known set of points for each conceptual object may potentially change somewhat frequently, enough so for computational expense in data structure management to be a concern. Are the answers to #1 and #2 still good, or are they expensive enough in setup/teardown to be likely to cause problems under this condition?

(I really do want to know the answers to these items separately, if they have distinct answers. Mega bonus points for any answers that generalize well to a Cartesian 4-space.)

Answer 1

I'd suggest a kd tree.

The nearest neighbour search is O(log Npoints) for randomly distributed points and you can easily extend the nearest neighbour search to account for occlusion.

However it's not ideal if lots of points move frequently. This may or may not make the kd-tree more expensive than other options depending on how often you need to rebuild it vs how many queries are done.

It will generalize to N dimensions.

Answer 2

I will point you to the page, which is one of the best resources in NN-search (Nearest Neighbors). It contains slides and links to other resources. But KD-tree is probably best solution (but there are many variants):

http://simsearch.yury.name/

There are great on-topic slides from Data structures of computer graphics course on CTU in Prague, by Vlastimil Havran:

http://dl.dropbox.com/u/5034466/dpg0904.pdf

Answer 3

1) Since speed is a concern, you may want to take a look at approximate nearest neighbor algorithms. I've used ANN in the past and it performed very well for around 12 dimensions. It lets you adjust desired precision so that you can have a trade off between speed and precision and find what works best.

2) Since your visual occlusion is a black-box one (I'm assuming unpredictable moving obstacles), I'm not sure if you have much of a choice other than doing occlusion tests on the points that the NN algorithm returned.

3) I don't believe ANN supports points changing, but I'm not sure since I didn't need that. It seems Cgal and Pastel support dynamic sets, but in terms of insertion/removal of points. Perhaps the papers here would also provide some insight.

I don't know if you need this advice, but I found that reusing libraries for such problems almost always is a better idea. There are so many pitfalls one can fall into while implementing the details. Good luck!