# Finding closest coordinate of a pre-known set

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.)

• The points are voxels with a fixed depth, width and height? May 31, 2011 at 21:33
• @Maik Semder: May be treated as such if you like. Jun 1, 2011 at 0:18
• So, I'm curious. Is the selection of 3/4-space geometrically motivated, or is operating on a data space that represents something else? For 1, are the arbitrary points inside or outside the hulls of the data points? For 2, closest visible point with reference to what? For 3, change in an arbitrary or pre-determined fashion (as in, do the objects have known configurations, or are you dealing with new points adding/subtracting)? And lastly, why would you want a 4-space generalization? Are you doing something with time or density as a dimension? Thanks for any clarification! Jun 7, 2011 at 3:38
• @ChrisE: Geometrically motivated. Could be either but typically outside. With reference to the same arbitrary point we're "looking" from in #1. Potentially arbitrary; points would typically not add/subtract but there will be cases where they will. I'm doing something with a 4th spatial dimension (ana/kata, W axis); it's not the main thing I want this for but it'd be helpful if my solution here generalized to it. Jun 7, 2011 at 14:05

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.

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

• kD trees my be problematic, if you want to move your points. (3) Let's say that the pre-known set of points for each conceptual object may potentially change somewhat frequently) Jun 4, 2011 at 7:43
• Than maybe GPGPU (if possible) sorting along the view axis will be solution (and should be realtime) Jun 4, 2011 at 8:27

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!