Mathematical technique to check intersection

Imagine there is a very very large room in the shape of a hollow cube. There are magic balls hanging in the air at fixed discrete positions of the room. No magic ball has another one exactly above it. If we take an imaginary horizontal plane of infinite area and pass through the cube, how can we be sure that the plane doesn't cut through any of the magic balls ?

The height of a magic ball is given as a function of its position (x and y). The distribution is such a way that some balls are at the same height while other are at different heights. Let the function be

z = axy + bx + cy

where a,b,c are positive integer constants. The positions (x-axis and y-axis values) and also the height (z) are discrete values (for simplicity, we can consider them positive integers).

If the ball distribution function was z=10xy+8x+4y, then it is impossible to have a z value of 15 or 21. So a plane at z=15 or z=21 would not cut any of the balls! In fact, in this case, any plane with a height (z = any odd number) would not cut through the balls. It is noticeable that there a some planes with height as even numbers that donot cut through the balls.

We do not want to find the heights of all the magic balls and compare it with the height of the horizontal plane, as that would be like trying all the possible combinations and would take very long time even on a computer.

Our aim is to find a fast method by which we can tell whether a given value of z (height) can be produced by any pair of (x,y) (positions).If a given z cannot be produced, then a plane at that height doesn't cu开发者_JS百科t through any balls! The question is also similar to finding whether a given number is present in a sequence produced by a function of two variables.

It would a great help if U could give me any suggestions to solve this problem. Thank You. (I have already tried evolutionary computing like GA,PSO,DE,SA etc. The method needs to be deterministic).

It sounds like you have a lot of balls in the room. The room height is from z=A to z=B. What you're interested in is whether any are at height z. To do that without necessarily iterating through all the balls, you need to start by assuming that the range A to B is empty and iterate through the balls, marking parts of this range as full, until it is either full completely or there are no balls. In the former case, no plane will satisfy, but you haven't iterated through all the balls to know that. In the latter case, you have ranges of z in which there are no balls and you can use these to check more than one plane easily, however at the initial cost of iterating through all balls.