1
$\begingroup$

I have points in a 3d world where their position is defined by 3 integers: X, Y, Z.

I'm searching for an algorithm / data structure to store these points in a way I can quickly find (e.g.: O(log(N)) the neighbour points in any direction aligned with the world axis (X-/left, X+/right, Y-/bottom, Y+/top, Z-/front, Z+/back).

Example:

  • Point 1 position: X=2, Y=1, Z=7
  • Point 2 position: X=4, Y=2, Z=7
  • Point 3 position: X=5, Y=1, Z=7
  • Point 4 position: X=8, Y=1, Z=7

I want to find the first neighbour on the right of the point 1. The algorithm should return me the first point where X>2, Y=1 and Z=7: it is the point 3.

Improve this question
$\endgroup$
2
  • $\begingroup$ In 3D, "on the right of" is meaningless. $\endgroup$
    – user16034
    Commented Feb 25, 2022 at 9:12
  • $\begingroup$ You don't tell us if the points are numerous and how they are spread. Nor if this is the most general query case. $\endgroup$
    – user16034
    Commented Feb 25, 2022 at 9:18

3 Answers 3

Reset to default
1
$\begingroup$

As stated, your query is for a point nearest to a coordinate plane, in a half space. A k-D tree structure seems ideal for such queries. You will need to adapt from a standard nearest neighbor query.

Improve this answer
$\endgroup$
0
$\begingroup$

I will define an $O(\log n)$ solution for X-right direction. The argument can be extended for the other directions also.

Let the input point set is: $(x_i,y_i,z_i)$ for $i \in \{1,\dotsc,n\}$. Suppose that for the coordinate $(y_i,z_i)$, we have a list of points that have $y = y_i$ and $z = z_i$. There can be at most $n$ such lists. Sort the points in each list by their $x$-coordinates.

When, a query point $(x_q,y_q,z_q)$ comes, perform a binary search in the list defined by $(y_q,z_q)$. This will give you the X-right neighbour of $(x_q,y_q,z_q)$ in $O(\log n)$ time.

The only remaining question is how to create the lists corresponding to each $(y_i,z_i)$, and locating these lists efficiently. For this, maintain a hash table that stores an entry corresponding to every $(y_i,z_i)$. The size of the table is $\Theta(n)$ and the key of the hash function corresponds to the pair $(y_i,z_i)$. Therefore, the lists for every $(y_i,z_i)$ can be created in average $O(n)$ time. Moreover, locating an entry $(y_q,z_q)$ from the hash table also takes $O(1)$ time on average; therefore queries can be answered efficiently.

Create these hash tables and lists for the remaining directions also. The total space complexity is just $O(n)$, and the preprocessing time is $O(n \log n)$ on average.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hash table should be pointing to balanced binary search trees for addition, deletion, and searching to be performed in O(logn) time. It will be better than a hash table pointing to lists (linked lists or array as a list). Doubly linked lists can give O(1) deletion. I think a balanced binary search tree will be better than maintaining a list and sorting it for binary search to work. If a linked list is used then a skip list would be required for binary search. So hash tables and BSTs will be a better approach, won't be? $\endgroup$
    – Adarsh Anurag
    Commented Sep 26, 2021 at 4:00
  • $\begingroup$ @AdarshAnurag I used the word "list" informally. I just wanted to give the idea. Basically, use any data structure that takes $O(\log n)$ search time. This can be done in many ways. For example, insert the elements in the linked list. After inserting all the elements, transfer them to an array and sort the array. Then, use the array for binary search purposes. Surely, balanced BST can also be used but you do not require it since we are not deleting anything and also the insertions are only taking place initially. So there are many possibilities :) $\endgroup$
    – Inuyasha Yagami
    Commented Sep 26, 2021 at 4:40
0
$\begingroup$

There are a number of spatial index solutions that can be used with 3D data. Most indexes belong to one of these groups: Quadtrees, R-trees and kD-trees and Locality Sensitive Hashing.

Most of these have floating point implementations, but they should work fine (or should be easily adaptable) to integer coordinates.

Many implementations support nearest neighbor search with custom distance functions, so it should be possible to write a distance function that return objects only for a given direction, e.g. by returning very large positive distance for points from the wrong directions.

One index that works especially well with integer coordinates is the (disclaimer: self-advertisement) PH-Tree, it is somewhat related to quatrees. One property it has is that it works "naturally" with integers (it can also encode floats (without loss of precision) but that is a bit complicated).

Improve this answer
$\endgroup$

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.