java - Multi-dimensional segment trees -

the problem have solve 4d version of 1d problem of stabbing queries: find intervals number belongs to. looking multi-dimensional implementation of segment trees. ideally, in java , use fractional cascading.

multi-dimensional implementations exist kd-trees (k-nn searches) , range trees (given bounding box, find points in it) segment trees i've found 1d implementations.

i'd happy consider other data structures similar space/time complexity address same problem.

to expand on comment, binary-space-partitioning algorithm have in mind this.

1. choose coordinate x , threshold t (random coordinate, median coordinate, etc.).
2. allocate new node , assign of intervals intersect half-plane x=t it.
3. recursively construct child nodes (a) intervals contained entirely within lower half-space x<t , (b) intervals contained entirely within upper half-space x>t.

the stabbing query starts @ root, checks of intervals assigned current node, descends appropriate child, , repeats. may worthwhile switch brute force small subtrees.

if many intervals getting stabbed half-plane x=t, try recursing on (a) intervals intersect lower half-space , (b) intervals intersect upper half-space. duplicates intervals, space requirement no longer linear, , have switch on brute force on collections of intervals subdivision proves unproductive.