Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $S \subset R^d$ be a convex polytope in $d$ dimensional real space. Say that $S$ has weight $w$ if there exists some basis $x_1,\ldots,x_d$ such that for every point $v \in S$, we can write $v = \sum_{i=1}^d \alpha_i x_i$ such that $\sum_{i=1}^d|\alpha_i| \leq w$. To avoid normalization issues, lets say that $S \subset [0,1]^d$, and that we must also choose the basis elements $x_i \in [0,1]^d$.

It is known that for every such set $S$, there exists a barycentric spanner: i.e. a set of points $x_1,\ldots,x_d \in S$ such that for every $v \in S$, $v =\sum_{i=1}^d \alpha_i x_i$ with $|\alpha_i| \leq 1$ for all $i$. In particular, this implies that every such set $S$ has weight at most $d$.

My question is whether there are any nontrivial conditions under which $S$ has weight $w < d$. (Of course there are some trivial conditions, like if $S$ is contained inside the $\ell_1$ ball of radius $w$...)

I am also interested in some relaxations of this goal: for example, perhaps the set of points $x_1,\ldots,x_m$ need not be linearly independent (but to avoid trivial solutions like taking the $x_i$ to be the vertices of the polytope, we would want some condition like $m < d^c$ for some constant $c$). Alternately, perhaps we only want an approximate representation: i.e. perhaps the guarantee is only that for each $v \in S$, there is a point $v'$ with $||v' - v||_{1} \leq \epsilon$ such that $v'$ has low weight.

Is anything known about questions like this?

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.