## Find a convex hull that contains given points?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Suppose that you have vectors $a_{1},...,a_{m}$ in $\mathbb{R}^n$. Can you take $n$ among them, let $v_{1},...,v_{n}$ such that $a_{1},...,a_{m}$ belong to the convex hull of $(cn)v_{1},-(cn)v_{1},...,(cn)v_{n},-(cn)v_{n}$ for some constant $c$?

My idea was to use gram-schmidt process where at step $i$ I choose the vector $u_{i}$ with the maximum euclidean norm. The answer would be those $a_{i}$'s that maximize the at each step the euclidean norm. Any ideas? Thanks

-
Even for the case where we have that $(c⋅n)v_{1},−(c⋅n)v_{1},...,(c⋅n)v_{n},−(c⋅n)v_{n}$ might help. Thanks! – unknown (yahoo) Feb 10 at 10:30

1
Except of Anton the others didn't understand the question i guess. First of all $c$ must be independent of $n$. Also you may assume that $a_{1},...,a_{m}$ span $R^n$ and then you have to find (if there exist) $n$ (as the dimension) vectors $v_{1},...,v_{n}$ s.t that $a_{1},...,a_{m}$ belong to the convex hull of $(c\sqrt{n})v_{1},-(c\sqrt{n})v_{1},...,$. Anton the fact is the number of initial vectors is $m = O(n^2)$, so I want sparse number of them... Thanks again! – unknown (yahoo) Feb 11 at 0:32

1
Can you do this for $m=n+1$? – Anton Petrunin Feb 11 at 2:18

1
Sure since $a_{1},...,a_{n+1}$ span $R^n$ we get that \lambda_{1}a_{1}+...+\lambda_{n} a_{n} + \lambda_{n+1}a_{n+1} =0 where the scalars are not all zero. Then divide by the one with maximum absolute value, let max the index: a_{max} = \sum_{i\neq max} \frac{\lambda_{i}}{\lambda_{max}}a_{i} with |\frac{\lambda_{i}}{\lambda_{max}}|\leq 1. Hence $a_{max}$ can be written as a convex combination of $nv_{1}-nv_{1},...,nv_{n},-nv_{n}$. Actually I want to solve it (If i can) for $(c\cdot n)v_{1},-(c\cdot)nv_{1},...$ – unknown (yahoo) Feb 11 at 7:07
I changed my answer. – Anton Petrunin Feb 11 at 19:41

## 3 Answers

Take $v_1,v_2,\dots,v_n$ which span parallelepiped of maximal volume. If $$a_i=x_1\cdot v_1+\dots+x_n\cdot v_n$$ then $|x_k|\le 1$, otherwise exchanging $v_k$ to $a_i$ will increase the volume. Hence $a_i$ belongs to the convex hull of $\{\pm n\cdot v_{i}\}$; i.e. $c=1$.

Below is the original answer to the original question.

If you agree to choose $N=\tfrac{n{\cdot}(n+1)}{2}$ points then you can get $c=1$.

Take the ellipsoid of smallest volume which contains all $\{a_i\}$. You may assume that ${a_i}$ is in generic position, in this case at most $N$ of the points lie on the boundary of ellipsoid; take them as $\{v_i\}$. If one of $a_i$ does not lie in the convex hull of $\{\pm\sqrt{n}\cdot v_i\}$ then you can decrease the volume of the ellipsoid, by pushing it in one direction and expanding in all the orthogonal directions.

-
Anton: The last version does not work since some $|x_k|$ could be (much) larger than $1$ and some (much) smaller. It is easy to construct examples with $n=2$ and $m=3$. – Misha Feb 11 at 22:33

2
@Misha: I do not think you are right; if $|x_i|>1$ once then you can increase the volume. – Anton Petrunin Feb 12 at 5:53

1
@Anton: Can you explain why by exchanging $u_{k}$ and $a_{i}$ the volume is increased? – unknown (yahoo) Feb 12 at 10:06
Observe that $v_{1},...,v_{n}$ are not orthonormal... – unknown (yahoo) Feb 12 at 10:18

1
The volume is the absolute value of determinant of matrix $A$ which has as columns the vectors $u_{1},...,u_{n}$. If you change $u_{1}$ with $a_{i} = x_{1}u_{1}+...+x_{n}u_{n}$ (let $|x_{1}|\geq 1$) then the volume of the new parallelepiped will be $|x_{1}||det(A)|$ is that right? I believe you are correct!!! – unknown (yahoo) Feb 12 at 10:29
show 1 more comment

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

This reduces to the problem of finding a set of linearly independent vectors with maximum cardinality. There are in general many such sets, but any of them is a solution if you pick $c$ large enough. Then the convex hull is an $n$-orthoplex (AKA cross-polytope). If you make $c$ big, it will include any set of points in the span of the set, including on particular $a_1,...,a_m$. Some googling reveals that an algorithm for finding such a set is here.

Or are you trying to produce a solution with minimum $c$? This is a much more interesting question, by which I mean that I don't know the answer (:-).

-

1
I think the question is whether a constant $c$ exists for which a solution is possible for all choices of $m$, $n$, $a_1,\ldots,a_m$. – Yoav Kallus Feb 10 at 16:13

This is just to say that I don't think choosing the vectors with the maximum Euclidean norm will suffice. In the example below, the two longest vectors (red) are collinear, and the hull derived from them—regardless of $c$—will be a line segment, which cannot contain the original (green) points.

-

the idea is to choose pairs $\pm v_i$ of maximal norm, IMHO... – Dima Pasechnik Feb 10 at 14:44
@Dima: Would not this example still lead to collinear $v_i$? – Joseph O'Rourke Feb 10 at 15:47
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 67, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9253247380256653, "perplexity_flag": "head"}