Range intersection with bounding box?
I think you can answer this in $O(n)$ time with a recursive algorithm, as follows.  It basically boils down to an ugly case analysis.

Over the real numbers

Let me start by assuming you are working over the real numbers, to make it easier to present the ideas.

Suppose the range is $(r_1,r_2,\dots,r_n) \ldots (s_1,s_2,\dots,s_n)$ and the bounding box has corners $(b_1,\dots,b_n)$ and $(c_1,\dots,c_n)$ with $b_i \le c_i$ for all $i$.  There are four cases:


If the intervals $[r_1,s_1]$ and $[b_1,c_1]$ don't overlap, then there is no overlap between your range and your bounding box.
If $r_1=s_1$ or $r_1=c_1$, then check whether $b_1 \le r_1 \le c_1$ and then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $r_1$ (i.e., the range is $(r_2,\dots,r_n) \ldots (\infty,\dots,\infty)$ and the box has corners $(b_2,\dots,b_n)$ and $(c_2,\dots,c_n)$).
If $r_1&lt;s_1$ and $s_1=b_1$, then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $s_1$  (i.e., the range is $(-\infty,\dots,-\infty) \ldots (s_2,\dots,s_n)$ and the box has corners $(b_2,\dots,b_n)$ and $(c_2,\dots,c_n)$).
Otherwise, the intervals $[r_1,s_1]$ and $[b_1,c_1]$ overlap at more than two points.  In this case, there is guaranteed to be an overlap between your range and your bounding box.  In particular, pick a value $x_1$ that is in the overlap and such that $r_1&lt;x_1&lt;s_1$; then $(x_1,b_2,\dots,b_n)$ is in the range and in the bounding box.


It is easy to see that this runs in $O(n)$ time, because the running time satisfies the recurrence $T(n) = T(n-1) + O(1)$.

Over the integers

If you are dealing with integers, then it suffices to add the following cases just before the "Otherwise":


If $s_1=r_1+1$, recurse twice: recurse on the range $(r_1,r_n,\dots,r_n)\ldots (r_1,\infty,\dots,\infty)$ and recurse again on the range $(s,-\infty,\dots,-\infty) \ldots (s_1,s_2,\dots,s_n)$ (leaving the bounding box alone).  If either of them finds a point of overlap, then you have found an overlap between your range and your bounding box.  (*)
If $c_1=b_1+1$, then there is a point of overlap.  (If $r_1&lt;b_1&lt;c_1\le s_1$, use $(b_1,\dots,b_n)$); if $r_1 \le b_1&lt;c_1 &lt; s_1$, use $(c_1,\dots,c_n)$); those are the only two possibilities.)


The running time with this modification remains $O(n)$.  It takes a little more work to see why, though.  Naively, we obtain the recurrence $T(n)=2 T(n-1) + O(1)$, due to need to recurse twice in the case marked (*); and this recurrence satisfies $T(n)=O(2^n)$, which is very bad.  Fortunately, this is an overly loose upper bound.  Note that when $(r_1,\dots,r_n) = (-\infty,\dots,-\infty)$ or $(s_1,\dots,s_n)=(\infty,\dots,\infty)$, then we never invoke the case (*) in any subsequent recursion.  So, when running on one of those inputs, the running time is $O(n)$.  Moreover, the case (*) recurses on inputs of this form.  Thus, we will never invoke case (*) more than once in the entire recursion tree.  Thus, the entire recursion tree can involve at most $2n$ recursive calls.  Thus, the total running time remains $O(n)$.

This algorithm looks a pretty messy, with at least 6 different cases.  Perhaps there is a cleaner way to do it.