2
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard♦ Jan 19 '19 at 21:30
  • $\begingroup$ Convex would do, but in general any shape that can be represented by a coherent set. $\endgroup$ – MrMeeSeeks Jan 19 '19 at 22:41
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Could you come up with strong assumptions about S that would change the picture? Because I couldn't. What kind of relaxations on the intersection would you imagine? Excluding one-point-intersection obviously yields little as you argued. No discrete space by the way. And thanks. $\endgroup$ – MrMeeSeeks Jan 20 '19 at 3:09
  • $\begingroup$ 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$. $\endgroup$ – Discrete lizard♦ Jan 20 '19 at 10:50
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard♦ Jan 20 '19 at 11:00

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.