# Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only interested in the design, no coding. I believe I can use the approach of kd-trees assuming that the query line is also axis aligned, say x-axis. Any help will be pretty much appreciated. Thanks in advance

• I can't understand what you are asking. Do you have a bunch of AABB and want to know which of them are intersected by a line? Nov 20, 2019 at 21:51

If your query line is x-axis aligned, this is essentially a 2D problem, as you can project all AABBs on the $$(y,z)$$-plane and answer the following question: Given $$n$$ axis aligned rectangles and a query point $$p$$, report the rectangles containing $$p$$.
To answer this question you can build a 2D segment tree. This is similar to a 1D segment tree, except that you start building your segment tree according to the projections of your rectangles on one dimension (say $$y$$) and instead of having some interval $$I$$ as a leaf, you replace it with a segment tree storing all projections on the $$z$$-axis of rectangles whose projection on the $$y$$-axis contain $$I$$.
You can then query a point by going down the tree and looking for all rectangles which are potential candidates according to their $$y$$-coordinates and then check among those which "fit" according to their $$z$$-coordinates.
This leads to $$O(n\log^2(n))$$ space used, $$O(\log^2(n))$$ time per query and $$O(n\log^2(n))$$ construction time.