0
$\begingroup$

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? (preferably quicker than $O(n)$; iterating over all ranges till one suitable is found)

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.

The reason why I post this anyway while there are other questions that help with my specific idea for a solution is because I also want to know if this is the most efficient way for my original problem; find if X is in any of n boxes.

If is helps, I expect all of those "boxes" to only have differing numeric values around one 2D plane, the end result is needed to "fence off" an A* neighbor search to specific "paths" it can navigate on.

$\endgroup$
5
  • 1
    $\begingroup$ I believe my answer to this question should give you some direction. (It is about reporting 2D boxes which contain a point, but the generalization to 3 dimensions is quite straight-forward) $\endgroup$
    – Tassle
    Commented Jan 31, 2020 at 13:47
  • $\begingroup$ @Tassle I already thought about that solution, the only thing I actually cant seem to find a good way of figuring out (as someone who has more experience with SE than CS) is what kind of data structure I need to get a query time (along that first 1D axis) that's faster than sequential linear-time search. $\endgroup$ Commented Jan 31, 2020 at 13:53
  • 1
    $\begingroup$ As stated in my response, you can use a Segment tree (which the Wikipedia article explains quite nicely in my opinion) to get a $O(\log(n))$ query-time in 1D. Now that is only beneficial if you want to do a bunch of queries on the same set of intervals, as it has a $O(n\log(n))$ preprocessing cost. For a single query (with no preprocessing) you can't do better than linear time. $\endgroup$
    – Tassle
    Commented Jan 31, 2020 at 14:01
  • $\begingroup$ Thanks, I'll give that algorithm a good look, and try to find a library (or write one myself) that implements it in the project I'm working on. Pre-processing is definitely going to happen, as I expect the tree to be static but queried multiple times each "time". After I've figure it out, I'll post the answer here to my own question. (but I invite anyone else for other suggestions) $\endgroup$ Commented Jan 31, 2020 at 14:08
  • $\begingroup$ I don’t quite understand the point of your question - can you simply check if x belongs to [L,R] for each interval in turn? It is not possible to do this in less than O(n) time with an arbitrary ordering of the intervals, since perhaps the only valid interval is the final one. $\endgroup$
    – Matthew C
    Commented Jan 31, 2020 at 20:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.