Vértice de un n-paralelepípedo más cercano a un punto. Método exhaustivo.

 

Sea $\mathcal{F}$ un n-paralelepípedo (sólido) generado por el conjunto de vectores linealmente independientes $B = \{\vec{b}_1,...,\vec{b}_n\}$. Sea $P\in\mathcal{F}$ un punto de dicho n-paralelepípedo. ¿Cuál es el vértice del n-paralelepípedo más cercano a $P$?

 Estrategia 1. Método exhaustivo.

Podemos calcular las coordenadas de todos los vértices del n-paralelepípedo.

Por ejemplo, en $\mathbb{R}^3$, los 8 vértices del paralelepípedo son:

$V_1 = \vec{0} = (0,0,0)$

$V_2 = \vec{b}_1$

$V_3 = \vec{b}_2$

$V_4 = \vec{b}_3$

$V_5 = \vec{b}_1 + \vec{b}_2$

$V_6 = \vec{b}_1 + \vec{b}_3$

$V_7 = \vec{b}_2 + \vec{b}_3$

$V_8 = \vec{b}_1 + \vec{b}_2 + \vec{b}_3$ 

Después calculamos la distancia de cada uno de ellos al punto $P$

$$d_i = \|P-V_i\|$$ 

 Y nos quedamos con el que tenga menor distancia (puede haber más de uno).

 

Ejemplo: Hagamos este método con un caso muy sencillo en $\mathbb{R}^2$.

$B=\{(30, 3), (5, 0)\}$ y el punto del paralelogramo $Q=(25.5, 2.5)$. Queremos hallar el vértice del paralelogramo más cercano a $Q$.

Los vértices del paralelogramo son:

$V_1=(0, 0); V_2=(30, 3); V_3=(5, 0); V_4=(35, 3)$

Y las correspondientes distancias al punto $Q$:

$d_1 \simeq 25.622255950637914$

$d_2 \simeq 4.527692569068709$

$d_3 \simeq 20.65187642806338$

$d_4 \simeq 9.513148795220223$ 

Por tanto, el vértice con menor distancia al punto $Q$ es $V_2=(30, 3)$.

 

Los cálculos han sido realizados con wxMaxima:

 

Contras del método exhaustivo.

Para dimensiones pequeñas el método exhaustivo es rápido y muy eficiente, pero para dimensiones grandes el coste computacional se incrementa exponencialmente, dado que el número de vértices de un n-paralelogramo es $2^n$.

Por ejemplo, en $\mathbb{R}^{100}$ tenemos $2^{100} = 1267650600228229401496703205376$ vértices.