Conjunto de vectores separados por al menos un ángulo especificado

Question

Supongamos theta y d son dadas.

¿Qué tamaño puede tener un conjunto de d-dimensional vectores tales que ningún par de ellos están en ángulo de menos de theta?

Particularmente, quiero un límite superior; es decir, n=n(theta,d) tal que dado n d-dimensional vectores, debe haber al menos 2 con ángulo de menos de theta entre ellos.

Por supuesto, la pregunta puede ser reescrita en todo tipo de formas, por ejemplo, los revestimientos de la superficie de la d-dimensional de la esfera por (d-1)-dimensional tapas de radio dado. etc.

El obligado no necesita ser ajustado. Algo por un factor de (constante)^d podría estar bien (aunque algo más exacto sería interesante también).

Answer 1

El nombre del sujeto que se busca es esférica códigos. Una buena referencia para este tema es Conway y Sloane "Esfera de Envases, Celosías, y de los Grupos." En el capítulo 9 se dan los detalles de la prueba para el mejor de los límites (creo que es debido a Levenstein, pero no tengo el libro conmigo).

Esto termina siendo relacionadas con la densidad de la esfera de envases. Hay una forma muy elegante, a prueba en el libro que relata la respuesta a su pregunta en la dimensión $n+1$ de la máxima densidad de la esfera de embalaje en la dimensión $n.$

Lo siento, no tenemos mis referencias conmigo, pero todo esto es en el capítulo 9 del libro.

Answer 2

Una manera de obtener un límite más bajo es el lema de Johnson-Lindenstrauss se aplican a una base orthonormal. Esto da forma exponencial muchos vectores tales que los ángulos entre todos los pares están arbitrariamente cerca de $\pi/2$.

http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma

Answer 3

Este es un estándar de construcción basado en el hecho de que el máximo de $\theta$-embalaje es también una $\theta$-net.

Fix $d$. Dado $\theta>0$, considere la posibilidad de $\theta$-embalaje de $S^d$; es decir, un conjunto de $n=n(\theta)$ $x_1,x_2,\dots,x_n$ $S^d$ tal que $|x_ix_j|>\theta$ (medimos intrínseca distancias en la esfera). Tenga en cuenta que

• $B(\tfrac\theta2,x_i)\cap B(\tfrac\theta2,x_i)=\varnothing$ $i\not=j$ y

• $\bigcup\limits_i B(\theta,x_i)=S^d$ ($\{x_1,x_2,\dots,x_n\}$ formulario $\theta$-netos en $S^d$)

Set $v(r)=\mathop{\rm vol}\{B(r,x)\subset S^d\}$. A continuación, $$n \cdot v(\tfrac\theta2) < \mathop{\rm vol}S^d < n\cdot v(\theta).$$ Claramente $1\le \tfrac{v(\theta)}{v(\theta/2)}\le 2^d$. Por lo tanto, $\mathop{\rm vol}S^d/v(\theta)$ da $n$ hasta un factor de $2^d$.