Find the intersection between two convex hulls, in this specific case

263 Views Asked by At

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, .

Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ be a function such that $d(k)$ decreases with $k$ (and the function $kd(k)$ increases with $k$).

We define the subset $S = \{d(\| \mathbf{v} \|_1)\mathbf{v}: \mathbf{v} \in V\}$. Let $C$ be its convex hull.

Let $S_1 = \{e \mathbf{v}: \| \mathbf{v} \|_1 =1; (\mathbf{v}\in V) \}$, for some $e \in \mathbb{R}_+$. We denote by $C_1$ the convex hull of $S_1$.

I need to find the intersection between $C$ and $C_1$ (we suppose that this intersection always exists..). An illustration of an example in 2D is given by the following figure:

enter image description here

How to find the coordinates of the points of intersection of $C$ and $C_1$ in the general case ? (there are 2 points in the above example).

Any hint is welcome.