Assume we have sets of the form

$$ M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\} $$

where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.

Goal

I am looking for an (explicit) representation of a function $f$, such that the minkowski sum $M$ is of the same form as the $M_j$, i.e.

$$ M = \sum_{j=1}^n M_j = \{x\in\mathbb{R}^d : f(x) \le 0,x\ge 0\} $$ where a Minkowski sum of sets is defined as

$$ A+B := \{x+y : x\in A, y\in B\}. $$

Inuition Building

Linear boundaries

Consider $f_j(x) = \langle w_j, x\rangle - b_j$. For $d=2$, we are really considering triangles.

d=2	d=3

Now in the case $d=2$, $n=2$ with linear $f_j$ boundaries the resulting set should intuitively look like this:

This is because you can choose the maximum $x_2^{(2)}$, where $$ x_2^{(j)} := \max \{x_2\in\mathbb{R}^d : (0, x_2) \in M_j\}, $$ from the set $M_2$ and add $M_1$ to get everything left of $x_1^{(1)}$, and then add $(x_1^{(1)}, 0)$ from $M_1$ to the entire set of $M_2$ to get the rest. That this is not just a subset of $M$ is intuitively clear, but more difficult to formalize.

Similarly for $n=4$ we have

So in some sense we are sorting the $w_j$ (or $f_j$) more generally.

Continuous Concave Boundaries

Intuitively this should generalize for concave, continuous $f_j$. This is because we can approximate $f_j$ with a polygonal chain and we know that we can then find sets with linear borders such that their minkowski sum has this polygonal chain as the border $$ M_j \approx \sum_{l=1}^k M_{jk} = \sum_{l=1}^k \{ x\in \mathbb{R}^d : \langle w_{jk}, x\rangle - b_{jk} \le 0, x\ge 0\} $$ So we get $$ \sum_{j=1}^n M_j \approx \sum_{j=1}^n \sum_{l=1}^k M_{jk} $$ which reduces this to the linear case. Making the approximation better and better should result in an equality in the limit.

Question

It feels like someone should have thought about this sort of thing already. But I can not find any sources. Probably because I don't know the names to look for. I looked a bit into linear programming, but since this is not an optimization problem per se I found it difficult to translate this into that. I am really looking for good notation to make this problem easier to think about.

At the moment I would struggle to translate the pictures into formal proofs - I might eventually manage to prove that my guess of $M$ is in fact $M$, but I do not see how that generalizes to higher dimensions where I can not just guess $M$ intuitively. So I am looking for a way where you can simply start calculating and $M$ is a result. That approach would likely generalize to higher dimensions.

Application

The application I have in mind is justifying the Production possibility fontier in economics, by combining the production capabilities of multiple individuals. This frontier is generally postulated to look like this:

https://en.wikipedia.org/wiki/Production%E2%80%93possibility_frontier#/media/File:Production_Possibilities_Frontier_Curve.svg

But no reason is provided. While our two dimensional case with four sets already has striking similarity, and if you assume a large populace with randomly distributed $w_j$ you can probably show that you get this type of curve in the limit.