I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane can make regions, some of them closed, and others not, the task is to count the number of points in each region.
I just need some ideas about how to solve, or if there is an algorithm for that.
Each of the plane can be considered as a constraint which might hold with =, <, or >. A point lies either on the plane or on one of the sides. This can be decoded by a +, - and 0. Say the string +++++----- decodes the cell for which the first 5 constraints hold with >, and the last 5 with <.
You can now go through all the possibilities. Start with the first plane and filter the points with respect to this plane. You will get three sets. Then use recursion to subdivide the sets further. If the recursion stops (that is you processed the 10th plane), you count the remaining set.
Regarding the running time. If you have $n$ points and $m$ planes then $$ T(n,m)= T(n_1,m-1)+T(n_2,m-1)+T(n_3,m-1) + O(n)$$ for $n_1+n_2+n_3=n$. This solves to $O(nm)$. You can use induction on $m$ to prove this.
A plane divides the 3D space in two regions. A good method to discern is to apply the plane equation to the point and see if it yields negative or positive result:
$$Ax + By + Cz + D = 0$$
is the equation of a plane in 3D. So if you put the point coordinates you'll get a positive, zero or negative number. (If zero, the point belongs to the plane and so, it's neither in either side of the plane.)
The question asks to count the points that belong to each of the delimited regions for each plane. Well, you have n planes each dividing the space in two halves (so you have $2^n$ regions at most, except in case you have paralell planes, but this procedure is applicable also in that case ---you'll get regions not accounted for as no point can lie in them), just consider each point and apply it to each plane. Then construct a number X, making bit $i$ (for plane $i$) of X a 1 in case applying plane to it gives a positive number and 0 in case applying it gives a negative one (in case it returns 0 you have to decide what side to count it ---what value you select for bit $i$--- for (if any) as this is a point that belongs to the plane) then with that number as a key for region X, increment counter of region X selected, so in one pass over all points you'll get all counters actualized with how many points belong to each region. Each key X, so constructed, identifies each of the possible regions you have divided the space into, so you must cope with $2^n$ regions (and counters) for $n$ planes.
