I have a problem at work where I have set of hyperrectangles, in no particular order, that do not overlap and when unioned create a hyperrectangle with no gaps. At the moment I am looking for a way to efficiently figure out which hyperrectangle a given coordinate is within.

I do not always have too many hyperrectangles, so just iterating through the set of partitioned hyperrectangles is often fine to see which one a given coordinate is in. However, I sometimes have larger quantities of hyperrectangles and I want to write something that scales better than simply iterating through the set.

My first thought is to consider some hashing approach analogous to spatial hashing but am not sure the best way to go about formulating this since the hyperrectangles could be any dimension. Any thoughts?


The best algorithm will depend on the proportion of hyperrectangles to dimensions. If I understand correctly, what you want is to do a first-pass computation where you build a data structure in order to get a sublinear algorithm (in terms of the number of hyperrectangles) that will tell you which hyperrectangle a point is in.

I think a binary search tree would work well. At each branch of the tree you can split the set of hyperrectangles in half by performing a check to see if coordinate X_i is greater than or less than some value. You want to include in each set every rectangle that is at least partially inside the split region. For example, if you have a rectangle from (0,0) to (2,2) and you split on the first coordinate at 1, you would want to include this rectangle in both sets. Continue until you have only single hyperrectangles - these will be the leaves of the tree.

How and when you split is up to you. Each time the number of hyperrectangles on both sides should be roughly equal. An approach where you just cycle through the dimensions would probably work well. For example, first you split halfway along X_1, then halfway along X_2, ... eventually you split halfway along X_d, then you start over if necessary.

If n is the number of hyperrectangles, then the construction step should take about O(n*log(n)), and the lookup step should take about O(log(n)) each time.

  • $\begingroup$ This sounds like a good approach and sounds similar in construction to a roughly balanced KD-Tree, which I have experience with. Let me try implementing this and get back to you. I feel this will work well for my purposes. $\endgroup$ – spektr Mar 14 '17 at 17:22
  • $\begingroup$ So I got an implementation working well. Used similar strategies to my KD-Tree implementations, but differed in that I needed to implement an explicit tree structure in this data structure while I can get away with an array-based tree form for the KD-Tree. I like this data structure compared to the naïve looping strategy because the loop strategy is $O(kN)$ search, where $k$ is the number of dimensions and $N$ is the number of subsets, while this data structure requires a $O(log(N))$ search I believe. Thanks for the insights! $\endgroup$ – spektr Mar 14 '17 at 22:03

Have you considered spatial indexes (other than spatial hashing)? It sounds like you could use a simple quadtree (up to 10 dimensions) or R-Tree (an R*Tree/RStarTree works well up to 50 dimensions or even more). In the case of R-Tree, an STR-Tree may be faster if you have can insert everything at once (bulk loading) rather than loading hyperrectangles one by one.

  • $\begingroup$ I have not considered these options, though these seem feasible. I am a little rusty on some of these geometric data structures other than KD-Trees, so I will have to read up the details about them. Thanks for the ideas! $\endgroup$ – spektr Mar 14 '17 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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