Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate
If all you have is a black-box function to test containment in your shape $S$, then the answer is no in general. For example, take $n=2$, let your rectangle $R$ have corners $(\pm1,\pm1)$ and let $S$ be a disk. Note that $S$ can have exactly 1 point of intersection with our rectangle and this can be any point on the boundary of the rectangle. So, since we work over $\mathbb{R}^2$, we have to test an infinite number of points and hence it is impossible. (obviously, if we have a discretized space, the rectangle has a finite number of points and we can simple test all of those.)



So, if you can have an intersection with only 1 point at an infinite number of places, it is impossible. This can happen for a large class of shapes. The first counter-example I can think of is when $S$ is an axis-parallel rectangle with a minimum side-length $w&gt;0$. $S$ can intersect at one point only in the 4 corners. If $S$ does intersect $R$, but not intersect in a corner $S$ must intersect a segment of length $w$ on the boundary of $R$, so we can test $\approx \frac{4}{w}$ values on the boundary of $R$ to find the intersection. 

Note that even in this case, you need $O(\frac{1}{w})$ tests to determine intersections. I think this means that unless you make some strong assumptions about $S$ or relax your condition of intersection, this problem is not solvable.