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

 
discard

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

Browse other questions tagged or ask your own question.