-1

This is part of a bigger problem, which is to find out if point XYZ exists in any of n (XYZ -> XYZ) "boxes".

I'm currently splitting up the problem into a smaller one, by focusing on one dimension first and "filtering" till either a range is found, or it's not;

How can I find out if my number X is in any of n ranges with only a "beginning" and an "end" number?

PS: I've already found some suggestions like "interval trees" and "segment trees", but I couldn't quickly find out if that was what I needed or not.

0

The problem that you've posted is unclear in the following:

  • Are you given one X and N ranges [L, R] or many X's for the same N ranges?
      — This makes a big difference in efficiency considerations.
  • Do you need to constantly modify the N ranges: adding/removing ranges, or adjusting L's and R's
      — This also makes a huge difference in efficiency considerations
  • Do you really just need to know if X is in any of the N ranges, or which of the N ranges?

Assuming then, that the ranges are constant and you want to look up many X's, you can precompute a data structure given the N ranges.

Depending on what you consider efficient, and on the total range of lowest L to highest R, you can either generate a total array or binary search array for the data structure, which goes to the how to index the array — direct indexing or binary search, respectively.

If you really only want to know whether X is in any of the ranges, the element type for the array is a boolean (yes/no), and for the binary search array, positions at range transitions and the boolean.

If you need to know which ranges X is an element of you might use a bit vector instead of a single boolean.


Still, this sounds like an XY problem.  It is difficult to generalize single dimensional solution to higher dimensions, so k-d trees or one of the many variants are probably be indicated.

| improve this answer | |

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.