Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the conditions:

  1. for every pair of points $p_i,p_j$ for $i,j\in\{1,\dots,n\}$ with $i\neq j$ there is a $k\in\{1,\dots,m\}$ such that $i,j\in\mathcal I_k$ holds.

  2. number of facets in convex hull of all the points in each of the index sets $\mathcal I_1,\dots,\mathcal I_m$ is $O(n)$ (the polytope $\mathcal P_k$ with vertex points indexed by with $p_i$ where $i\in\mathcal I_k$ can be defined by intersection of $O(n)$ half spaces at every $k\in\{1,\dots,m\}$).

My problem is what is the worst case $m$ do I need?

Does $m=polylog(n)$ hold if $d=polylog(n)$ holds?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.