2
$\begingroup$

I'm new to CS and being aware of what algorithms exist, but what data structure allows you to have fast lookups of single points within a distance in 3d?

e.g. (with 2d circles instead of 3d spheres)

enter image description here

I would expect the first location to return null, and the second one to return circle a.

Circles can not overlay, circles/spheres differ in radius.

I would assume this to be nearest neighbor, but maybe some optimizations can be made considering you are often outside the area?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

I would not use a nearest neighbor query, they tend to be expensive compared to window query or range query. However, most indexes that support nearest neighbor also support window queries.

You can use any spacial index that supports shapes, quadtree, R-Tree (especially RStarTree), ...:

  • Insert your circles into the index. This is often only supported as inserting rectangles, so you may have to insert the MMB (minimum bounding box).
  • For querying, indexes commonly support window queries (rectangular, axis-aligned windows(boxes)). Just set the window size to 0 by defining the min/min/min corner and max/max/max corner of the query to be equal to your search point. This should return all MBBs that intersect with your search point.
  • Finally, for all returned circles, you have to manually calculate whether they really intersect with your search point (they may not intersect because the MBB is larger than the circle.

For example-implementations (Java) of various spatial indexes have a look here (shameless self advertisement).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't understand why you expect them to be expensive. This is in 3D, and in 3D, my understanding is that they are not expensive -- it's higher-dimensional data where they tend to be problematic. Moreover as far as I can tell the alternative data structures you mention are also instances of nearest neighbor data structures. Am I missing something? $\endgroup$
    – D.W. ♦
    Commented Feb 16, 2018 at 2:56
  • $\begingroup$ Expensive is relative. NN (nearest neighbor) is more expensive than window queries (which are comparably cheap), in low dimensions as well as in high dimensions. And of course (almost?) any operation in high dimensions are more expensive than low dimensions. $\endgroup$
    – TilmannZ
    Commented Feb 17, 2018 at 15:52
1
$\begingroup$

You could in principle use any data structure for nearest neighbor search, of which there are many. Your specific version of the problem is known as fixed-radius near neighbors, and there are many solutions in the literature that are optimized for this particular version of the problem.

One simple solution is to overlay a grid, map every point to its grid square, and then do lookups by looking at all points in the same and adjoining grid squares. Since you are in 3D space, you'll only have to look at 27 grid squares (assuming you make the width of each grid square equal to the fixed distance), so this should allow for essentially constant-time operations.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What would the name be when the delta can change? $\endgroup$
    – Ryan Leach
    Commented Feb 16, 2018 at 2:38
  • $\begingroup$ @RyanTheLeach, then I suspect it's basically just nearest neighbor search. Some of the data structures allow early stopping of the search once you've hit the fixed distance. $\endgroup$
    – D.W. ♦
    Commented Feb 16, 2018 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.