# Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate

Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape,

is it possible to calculate whether the box intersects the shape?

• What is a "shape" here? As long as this shape has one isolated point, it is clearly impossible, so the shape will have to be regular in some sense. – Discrete lizard Jan 19 '19 at 21:30
• Convex would do, but in general any shape that can be represented by a coherent set. – MrMeeSeeks Jan 19 '19 at 22:41

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>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.
• I think that it might be nessecary to assume $S$ is a union of axis-parallel (assuming $R$ is axis-parallel) (hyper)rectangles of minimum width $w$. Otherwise, (I think) $S$ can always be translated such that it only intersects an arbitrary small segment or point on some boundary of $R$. – Discrete lizard Jan 20 '19 at 10:50
• What I mean by relaxations is, for example, you are fine with having a algorithm that finds an intersection only if the intersection is 'nice', e.g. it contains a ball of radius at least $\varepsilon$. In this case, there is a finite sized grid of points in $R$ of which at least one lies in $S$ if the intersection is 'nice'. But I think that the main takeaway is that it is likely that this formalization is not a good way to solve your problem, i.e. it is genarally not possible to find all intersections when we can only query containment for one shape, so try something else. – Discrete lizard Jan 20 '19 at 11:00