Enumerate all allocations of points in a simplex Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process: 


Fix two positive weights $(w_x,w_y)$;
For each point $(x,y)\in M$, calculate $w_x x$ and $w_y y$;
If $w_x x &gt; w_y y$ then give the point to X; else give the point to Y.


From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why? Because if a point $(x_1,y_1)$ is given to X, then all the points $(x_2,y_2)$ with $x_2&gt;x_1,y_2&lt;y_1$ are given to X too. Thus, each allocation can be found by cutting the line at some point,  giving to X all the points between the cut and $(1,0)$, and giving to Y the remaining points. Thus, it is easy to enumerate all possible allocations.

The question is: what happens when we move to a higher-dimensional simplex? For example, consider the standard 3-simplex $\{(x,y,z)~|~x+y+z=1~;~ x,y,z\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y or to Z by the following process: 


Fix 3 positive weights $(w_x,w_y,w_z)$;
For each point $(x,y,z)\in M$, calculate $w_x x$ and $w_y y$ and $w_z z$;
If $w_x x$ is larger than the other two - give the point to X; else, if $w_y y$ is larger than $w_z z$ - give the point to Y; else, give the point to Z.


What is an efficient algorithm, with run-time polynomial in the output size, for enumerating all and only the allocations attainable by the above procedure?
I'd suggest using a recursive search.  Suppose you have a subset of $k$ of the points and a proposed allocation for those $k$ points into X/Y/Z.  Then you can test whether there exists $w_x,w_y,w_z$ that would lead to that allocation, by testing feasibility of a linear program.  (For the allocation to be feasible, there are a bunch of linear inequalities that must hold on the variables $w_x,w_y,w_z$; test whether these can all simultaneously hold.)

Now, given a feasible allocation for $k$ points, pick one more point and try all three possibilities for whether that additional point is allocated to X, Y, or Z.  (In other words, you extend it to three possible allocations on $k+1$ points.)  Test which ones are feasible, and recurse on each of the feasible ones.

One can show that if there are $N$ feasible allocations in all, then this process will require at most $3mN$ recursive invocations.  Each recursive invocation involves solving a linear program, which can be done in polynomial time.  Thus, we obtain a procedure whose running time is polynomial in the number of feasible allocations.  The same result generalizes to more than three dimensions.