Is there any efficient algorithm for determining whether a function is $0$ anywhere in some range?

Question

Here is my problem in a nutshell. I wanted to detect collisions between lots of different 2D and 3D shapes in a computer program. A lot of them are pretty simple shapes but I was hoping to maybe improve it a little. It occurred to me that I could use indicator functions to improve the collisions.

Suppose there are two objects f and g with indicator functions $f(x)$ and $g(x)$, where $x$ is a point. Basically the functions return 1 if is in the shape and $0$ if not.

I know that $1 - f(x)g(x)$ is the indicators function for the regions where there's isn't a collision. I wish rob find I find it $0$ anywhere. Seems like an iterative product might work but that's wouldn't work for a computer.

I'm looking for mathematics stance on this. Efficiency is only a concern in the sense that I need it to be performance.

Edit: In hindsight I cannot think of any situation in which the individual functions won't be piecewise continuous

Answer 1

You mean, is there any better strategy than checking every point $x \in G$ and see if the indicator function vanishes, e.g. $\chi(x) = 0$?

(Source: Wikipedia)

This would mean that you have extra information that would allow you to skip certain parts of $G$ from inspection.

There are techniques like bounding volumes and putting them into a spatial hierarchical order, that allow such short cuts.

Answer 2

If the function $$f(z) = f(x+iy) = f_r(x+iy) + i\cdot f_i(x+iy)$$ is differentiable and complex analytic with real part $f_r(z)$ and imaginary part $f_i(z)$, all partial derivatives below must be continous and also:

$$\text{Cauchy-Riemann equations for analyticity: }\left\{\begin{align}\frac{\partial f_r}{\partial x} = &\phantom{-.}\frac{\partial f_i }{\partial y}\\\frac{\partial f_r}{\partial y} = &-\frac{\partial f_i}{\partial x}\end{align}\right\}$$

or mereomorphic (have a finite countable number of poles, but no essential singularity). Then you could do Cauchy argument variation to count the number of zeros inside a contour. That would be a well defined calculation to do as long as you can exclude any non-real roots and poles.

This could be achieved by for example making sure that $C$ includes an infinitesimally thin rectangular slice along the real line: $$\text{Integral line segments } : C=\lim_{\epsilon \to 0} \cases{1) [a,b] - i\epsilon\\ 2)[b-i\epsilon,b+i\epsilon]\\3)[b,a]+i\epsilon\\4)[a+i\epsilon,a-i\epsilon]}$$

And then calculate this integral and solve for $N$:

$$\oint_{C}\frac{f'(z)}{f(z)}dz = 2\pi i(N-P)$$

That no poles will occur is ensured by $P=0$ which comes from continuity.