<p>I'd suggest using a recursive search.  Suppose you have a subset of <span class="math-container">$k$</span> of the points and a proposed allocation for those <span class="math-container">$k$</span> points into X/Y/Z.  Then you can test whether there exists <span class="math-container">$w_x,w_y,w_z$</span> 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 <span class="math-container">$w_x,w_y,w_z$</span>; test whether these can all simultaneously hold.)</p>

<p>Now, given a feasible allocation for <span class="math-container">$k$</span> 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 <span class="math-container">$k+1$</span> points.)  Test which ones are feasible, and recurse on each of the feasible ones.</p>

<p>One can show that if there are <span class="math-container">$N$</span> feasible allocations in all, then this process will require at most <span class="math-container">$3mN$</span> 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.</p>

CC BY-SA 4.0
2019-03-09T23:10:14.083Z
If I understand correctly, your algorithm does a depth-first search on the tree of allocations. In this tree, each node in depth $i$ corresponds to a feasible allocation of points $1,...,i$. The root is the empty allocation. Each node in depth $i<m$ has at most 3 children - one for each possible allocation of point $i+1$. There are $N$ leaves - one for each complete feasible allocation. Is this description correct?
Erel Segal-Halevi
CC BY-SA 4.0
2019-03-09T23:16:52.283Z
@ErelSegal-Halevi, yup.  Except, once we find that a partial allocation is not feasible, we don't explore anything under that node.  It's easy to see that if there are N feasible allocations, then we only visit nodes that are ancestors of those N leaves (plus their siblings), and the number of those is the height of the tree times N times the branching factor of the tree.  (I've corrected a small error in the last paragraph of my answer regarding the number of recursive invocations.)
D.W.
CC BY-SA 4.0
2019-03-13T10:42:56.360Z
Great answer, and a useful general technique. Thanks. How can I cite your answer in a paper?
Erel Segal-Halevi
CC BY-SA 4.0
2019-03-13T15:47:49.793Z
@ErelSegal-Halevi, glad it helped!  You could cite this this question/answer (see e.g. the "cite" link under the question and answer).
D.W.
CC BY-SA 4.0
2019-03-08T01:17:37.180Z
2019-03-09T23:17:00.550Z
2019-03-09T23:17:00.550Z
D.W.
<blockquote>
  <p>From the set of <span class="math-container">$2^m$</span> possible allocations, only <span class="math-container">$m+1$</span> allocations can be attained by the above procedure. Why?</p>
</blockquote>

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

<p>Now, lift this into 3D. Without loss of generality, either <span class="math-container">$w_x = 0$</span> and it reduces to the 2D situation, or <span class="math-container">$w_x = 1$</span>. In the latter case, for each allocation between X and Y we have <span class="math-container">$\frac{x_i}{y_i} \le w_y &lt; \frac{x_{i+1}}{y_{i+1}}$</span>. Now we consider the range of values which <span class="math-container">$w_z$</span> can take. The points allocated to X can be sorted by the value of <span class="math-container">$w_z$</span> at which they are on the boundary, and the points allocated to Y can be sorted by the value of <span class="math-container">$w_z$</span> at which they are on the boundary for an arbitrary fixed <span class="math-container">$w_y$</span>. We can combine the chains by using the constraints on the possible range of <span class="math-container">$w_y$</span> 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.</p>

CC BY-SA 4.0
2019-03-09T23:21:34.977Z
What is $i$ in the second paragraph? And, what is the "resulting DAG with cutoffs for Z"?
Erel Segal-Halevi
CC BY-SA 4.0
2019-03-09T23:48:36.740Z
$i$ is the loop variable indicating where you make the allocation division between X and Y. Effectively, it's the number of points allocated to X in the initial X-Y allocation. You're mis-parsing the ambiguous noun phrase in the last sentence: it's (the possible topological sorts on the resulting DAG) with (cutoffs for Z). For each topological sort you do the same thing of picking one of the $n+1$ places to allocate between (X+Y) vs Z. But the topo. sorts aren't independent: if you choose to allocate the first three points to Z, you don't care about the order of points beyond the cutoff.
Peter Taylor
CC BY-SA 4.0
2019-03-11T17:42:57.703Z
OK. So the algorithm has two steps: constructing a DAG where the nodes are the $m$ points, and finding all topological sorts in that DAG. Is it correct?
Erel Segal-Halevi
CC BY-SA 4.0
2019-03-08T13:44:55.077Z
2019-03-08T13:54:06.523Z
2019-03-08T13:54:06.523Z
Peter Taylor
<p>Consider the standard 2-simplex <span class="math-container">$\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$</span>.
Given a set <span class="math-container">$M$</span> of <span class="math-container">$m$</span> points in this simplex, we allocate each point either to X or to Y by the following process: </p>

<ul>
<li>Fix two positive weights <span class="math-container">$(w_x,w_y)$</span>;</li>
<li>For each point <span class="math-container">$(x,y)\in M$</span>, calculate <span class="math-container">$w_x x$</span> and <span class="math-container">$w_y y$</span>;</li>
<li>If <span class="math-container">$w_x x &gt; w_y y$</span> then give the point to X; else give the point to Y.</li>
</ul>

<p>From the set of <span class="math-container">$2^m$</span> possible allocations, only <span class="math-container">$m+1$</span> allocations can be attained by the above procedure. Why? Because if a point <span class="math-container">$(x_1,y_1)$</span> is given to X, then all the points <span class="math-container">$(x_2,y_2)$</span> with <span class="math-container">$x_2&gt;x_1,y_2&lt;y_1$</span> 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 <span class="math-container">$(1,0)$</span>, and giving to Y the remaining points. Thus, it is easy to enumerate all possible allocations.</p>

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

<ul>
<li>Fix 3 positive weights <span class="math-container">$(w_x,w_y,w_z)$</span>;</li>
<li>For each point <span class="math-container">$(x,y,z)\in M$</span>, calculate <span class="math-container">$w_x x$</span> and <span class="math-container">$w_y y$</span> and <span class="math-container">$w_z z$</span>;</li>
<li>If <span class="math-container">$w_x x$</span> is larger than the other two - give the point to X; else, if <span class="math-container">$w_y y$</span> is larger than <span class="math-container">$w_z z$</span> - give the point to Y; else, give the point to Z.</li>
</ul>

<p>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?</p>

<ds.algorithms><simplex>
Enumerate all allocations of points in a simplex
Erel Segal-Halevi
# Enumerate all allocations of points in a simplex

(Asked by: username_0 on 2019-03-07)

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 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?

**Tags:** ds.algorithms, simplex


---

## 2 answers

### Answer by username_1 on 2019-03-08. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: If I understand correctly, your algorithm does a depth-first search on the tree of allocations. In this tree, each node in depth $i$ corresponds to a feasible allocation of points $1,...,i$. The root is the empty allocation. Each node in depth $i<m$ has at most 3 children - one for each possible allocation of point $i+1$. There are $N$ leaves - one for each complete feasible allocation. Is this description correct?  
> **username_1**: @ErelSegal-Halevi, yup.  Except, once we find that a partial allocation is not feasible, we don't explore anything under that node.  It's easy to see that if there are N feasible allocations, then we only visit nodes that are ancestors of those N leaves (plus their siblings), and the number of those is the height of the tree times N times the branching factor of the tree.  (I've corrected a small error in the last paragraph of my answer regarding the number of recursive invocations.)  
> **username_0**: Great answer, and a useful general technique. Thanks. How can I cite your answer in a paper?  
> **username_1**: @ErelSegal-Halevi, glad it helped!  You could cite this this question/answer (see e.g. the "cite" link under the question and answer).  

---

### Answer by username_2 on 2019-03-08. Score: 0

> 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.

> **Comments:**
> **username_0**: What is $i$ in the second paragraph? And, what is the "resulting DAG with cutoffs for Z"?  
> **username_2**: $i$ is the loop variable indicating where you make the allocation division between X and Y. Effectively, it's the number of points allocated to X in the initial X-Y allocation. You're mis-parsing the ambiguous noun phrase in the last sentence: it's (the possible topological sorts on the resulting DAG) with (cutoffs for Z). For each topological sort you do the same thing of picking one of the $n+1$ places to allocate between (X+Y) vs Z. But the topo. sorts aren't independent: if you choose to allocate the first three points to Z, you don't care about the order of points beyond the cutoff.  
> **username_0**: OK. So the algorithm has two steps: constructing a DAG where the nodes are the $m$ points, and finding all topological sorts in that DAG. Is it correct?  

---

