most recent 30 from http://mathoverflow.net 2013-05-20T02:43:16Z http://mathoverflow.net/feeds/question/16879 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16879/set-of-vectors-separated-by-at-least-a-specified-angle Matt Richards 2010-03-02T17:18:58Z 2010-03-04T04:05:58Z

<p>Suppose theta and d are given.</p> <p>How big can a set of d-dimensional vectors be such that no pair of them are at angle less than theta?</p> <p>I particularly want an upper bound; that is, an n=n(theta,d) such that given n d-dimensional vectors, there must be at least 2 with angle less than theta between them.</p> <p>Of course, the question can be rewritten in all sorts of ways, for example, coverings of the surface of the d-dimensional sphere by (d-1)-dimensional caps of given radius etc etc... </p> <p>The bound doesn't need to be tight. Something out by a factor of (constant)^d might be fine (although something more exact would be interesting too).</p> <p>Thanks!</p> <p>Matt</p>

http://mathoverflow.net/questions/16879/set-of-vectors-separated-by-at-least-a-specified-angle/16886#16886 Anton Petrunin 2010-03-02T18:07:30Z 2010-03-04T04:05:58Z

<blockquote> <p>This is a standard construction based on the fact that maximal $\theta$-packing is also an $\theta$-net.</p> </blockquote> <p>Fix $d$. Given $\theta>0$, consider $\theta$-packing of $S^d$; i.e. a set of $n=n(\theta)$ points $x_1,x_2,\dots,x_n$ in $S^d$ such that $|x_ix_j|>\theta$ (we measure intrinsic distances in the sphere). Note that </p> <ul> <li><p>$B(\tfrac\theta2,x_i)\cap B(\tfrac\theta2,x_i)=\varnothing$ for $i\not=j$ and </p></li> <li><p>$\bigcup\limits_i B(\theta,x_i)=S^d$ (i.e. ${x_1,x_2,\dots,x_n}$ form a $\theta$-net in $S^d$)</p></li> </ul> <p>Set $v(r)=\mathop{\rm vol}{B(r,x)\subset S^d}$. Then $$n \cdot v(\tfrac\theta2) &lt; \mathop{\rm vol}S^d &lt; n\cdot v(\theta).$$ Clearly $1\le \tfrac{v(\theta)}{v(\theta/2)}\le 2^d$. Thus, $\mathop{\rm vol}S^d/v(\theta)$ gives $n$ up to factor $2^d$.</p>

http://mathoverflow.net/questions/16879/set-of-vectors-separated-by-at-least-a-specified-angle/16889#16889 Bill Johnson 2010-03-02T18:31:53Z 2010-03-02T18:31:53Z

<p>One way of obtaining a lower bound is to apply the Johnson-Lindenstrauss lemma to an orthonormal basis. This gives exponentially many vectors such that the angles between all pairs are arbitrarily close to $\pi/2$.</p> <p><a href="http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma" rel="nofollow">http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma</a></p>

http://mathoverflow.net/questions/16879/set-of-vectors-separated-by-at-least-a-specified-angle/16942#16942 Ben Weiss 2010-03-03T01:40:16Z 2010-03-03T01:40:16Z

<p>The subject name you are looking for is <a href="http://en.wikipedia.org/wiki/Spherical_code" rel="nofollow">spherical codes</a>. A good reference for this subject is Conway and Sloane's "<a href="http://www2.research.att.com/~njas/doc/splag.html" rel="nofollow">Sphere Packings, Lattices, and Groups</a>." In chapter 9 they give the details of the proof for the best bounds (I believe it is due to Levenstein, but don't have the book with me).</p> <p>This ends up being related to density of sphere packings. There's a very elegant proof in the book which relates the answer to your question in dimension $n+1$ to the maximal density of sphere packing in dimension $n.$</p> <p>Sorry I don't have my references with me, but this is all in chapter 9 of the book.</p>