Enumerate all allocations of points in a simplex

Question

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 > 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>x_1,y_2<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?

Answer 1

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.

Answer 2

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why?

The boundary between the two halves of the allocation is the line $w_xx = w_yy$; the point $(x, y)$ only crosses from one half to the other when it's on the boundary, so we can sort the points by $\tan^{-1}(y,x)$.

Now, lift this into 3D. Without loss of generality, either $w_x = 0$ and it reduces to the 2D situation, or $w_x = 1$. In the latter case, for each allocation between X and Y we have $\frac{x_i}{y_i} \le w_y < \frac{x_{i+1}}{y_{i+1}}$. Now we consider the range of values which $w_z$ can take. The points allocated to X can be sorted by the value of $w_z$ at which they are on the boundary, and the points allocated to Y can be sorted by the value of $w_z$ at which they are on the boundary for an arbitrary fixed $w_y$. We can combine the chains by using the constraints on the possible range of $w_y$ to place cross-chain constraints: for each point allocated to Y, find the latest point allocated to X which is forced to precede it, and the earliest point allocated to X which is forced to follow it. Then the possible allocations between X,Y,Z are given by the possible topological sorts on the resulting DAG with cutoffs for Z.