February 22, 2009 by mchouza

Equidistancia en R^n (parte II)

[Continuación de “Equidistancia en R^n (parte I)“]

Mientras investigaba este problema encontré descrito el siguiente “truco”:

Yes, this linearization trick is pretty standard in computational
geometry. The specific variation you use, mapping a vector v onto
(v,|v|^2), turns circles or more generally spheres in d dimensions
into planes or more generally hyperplanes in d+1 dimensions. Your
equation

     | (x^2  + y^2)   x   y   1 |
     | (x1^2 + y1^2)  x1  y1  1 |  = 0
     | (x2^2 + y2^2)  x2  y2  1 |
     | (x3^2 + y3^2)  x3  y3  1 |

is the standard equation for a plane through three points
(xi,yi,xi^2+yi^2).

Para ver como funciona, podemos partir de la ecuación de una hiperesfera en $\mathbb{E}^n$ (o sea una (n-1)-esfera):

$\sum_{i=1}^n (x_i - a_i)^2 = R^2$ .

Si expandimos el cuadrado podemos obtener la siguiente ecuación

$\sum_{i=1}^n (x_i^2 - 2 a_i x_i + a_i^2) = R^2$ ;

reuniendo las constantes en el segundo miembro quedaría

$\left(\sum_{i=1}^n x_i^2\right) - \sum_{i=1}^n 2 a_i x_i = R^2 - \sum_{i=1}^n a_i^2$ .

Esto es claramente la ecuación de un plano en un espacio con la “nueva coordenada” $\sum_{i=1}^n x_i^2$ . Como es equivalente a la ecuación de la hiperesfera mostrada anteriormente, todos los puntos que estén en ese plano y cumplan la condición de que la coordenada adicional sea $\sum_{i=1}^n x_i^2$ estarán en la hiperesfera y viceversa.

En el próximo post veremos como se puede aplicar este truco para obtener algunos resultados sobre las hiperesferas en $\mathbb{E}^n$ .

February 22, 2009 by mchouza

Equidistancia en R^n (parte I)

Se denomina como conjunto equilátero de puntos a aquel cuyos miembros se encuentran a igual distancia entre si. En $\mathbb{E}^n$ , por ejemplo, los vértices de un triángulo equilátero forman un conjunto de esta naturaleza.

Podemos observar que en $\mathbb{E}^2$ el conjunto equilátero con mayor cantidad de puntos es el de los vértices de un triángulo equilátero que contiene (obviamente) tres puntos. Si estudiamos los conjuntos similares en $\mathbb{E}^3$ , veremos que el mayor conjunto equilátero es el que contiene los vértices de un tetraedro regular, compuesto por 4 puntos.

Una conjetura razonable en base a estas observaciones es suponer que la máxima cantidad de puntos que puede contener un conjunto equilátero en un espacio euclidiano de dimensión n es n + 1. En efecto, esto es lo que sucede; de hecho, este resultado ha sido denominado “obvio”… No siendo matemático, desconozco porque es considerado “obvio” y, por lo tanto, voy a intentar estudiarlo en los siguientes posts de esta “serie” 😀 .

February 14, 2009 by mchouza

Un problema de integrales (III)

[Continuación de “Un problema de integrales (II)“]

En este último post relativo al problema veremos como puede encontrarse una versión “redondeada” de la trayectoria poligonal hallada en el post anterior. Para ello debemos empezar definiendo una forma específica en la que se llevará a cabo el proceso de “redondeo”.

Una forma simple de evitar discontinuidades es utilizar interpolación lineal para reemplazar las discontinuidades por “rampas”. La función de control que utilizaremos (encontrada mediante el bien conocido método de prueba y error 🙂 ) puede describirse como interpolando linealmente entre los siguientes pares tiempo – orientación:

$(0, 0)$ , $(0.2, 0)$ , $(0.3, \theta_1)$ , $(0.7, \theta_2)$ , $(0.8, \theta_3)$ y $(1, \theta_3)$ .

Entonces, por ejemplo, tendremos:

$\theta(0.4) = \frac{0.4 - 0.3}{0.7 - 0.3}\theta(0.7) + \frac{0.7 - 0.4}{0.7 - 0.3}\theta(0.3) = \frac{1}{4}\theta_2+ \frac{3}{4}\theta_1$ .

Aplicando las restricciones encontradas en el post original a esta función de control parametrizada, encontramos que la primera ecuación se cumple trivialmente por la forma de la familia de funciones de control elegida y las otras quedarán como

$\int_0^1 e^{-i \theta(t; \theta_1, \theta_2, \theta_3)} dt = F(\theta_1, \theta_2, \theta_3) = 0$ y

$\int_0^1 t e^{-i \theta(t; \theta_1, \theta_2, \theta_3)} dt = G(\theta_1, \theta_2, \theta_3) = 0$ .

La forma de las funciones $F$ y $G$ es en general demasiado compleja como para permitir una solución analítica (al menos una utilizando los métodos que conozco), pero es posible buscarla por métodos numéricos. Si partimos desde $\theta_1 = 2\pi$ , $\theta_2 = \pi$ y $\theta_3 = 2\pi$ , FindRoot encuentra la siguiente solución:

$\theta_1 \to 3.3895398221083102286...$

$\theta_2 \to 3.2322701447530641984...$

$\theta_3 \to 6.6218099668613744270...$ .

Los residuos dados por los valores de $\theta_1$ , $\theta_2$ y $\theta_3$ con la precisión calculada (1000 decimales) dejan residuos menores que $10^{-995}$ , por lo que es razonable asumir que la solución es real y no un “numerical artifact”.

Graficando la trayectoria:

Gráfico de la trayectoria

Detalle del final de la trayectoria, donde se observa que es oblicua al eje X.

Tal como se observa en la última figura, el valor de $\theta(1)$ dista mucho ser nulo. En efecto, es $0.33862465968178795010...$ .

Resumiendo, hemos construido una función $\theta(t)$ que satisface la tres ecuaciones

$\theta(0) = 0$ ,

$\int_0^T e^{-i \theta(t)} dt$ y

$\int_0^T t e^{-i \theta(t)} dt$

para $T = 1$ y manteniendo la derivabilidad de $\theta(t)$ .

Cabe hacer varias objeciones a esta solución: en primer lugar, puede que haya entendido mal el problema 😀 ; también es posible que la función continua y lineal a trozos no se “suficientemente derivable”. Siempre sería posible repetir el análisis utilizando una partición diferenciable de la unidad para obtener una función $\theta(t)$ que sea $C^{\infty}$ , aunque dudo que esto lleve a un resultado distinto.

Voy a consultarle al autor original del problema para conocer su opinión del contraejemplo; probablemente se refiriera a otra cosa que el problema desarrollado en esta serie de posts pero no se pierde nada preguntando :-). Y ciertamente fue un problema interesante para tratar.

Para terminar, una animación de la trayectoria recorrida con velocidad unitaria y aceleración unitaria:

Animación de la trayectoria. Las flechas representan las velocidades de cada uno de los puntos y puede apreciarse que permanecen paralelas en todo momento.

February 12, 2009 by mchouza

Un problema de integrales (II)

[Continuación de “Un problema de integrales (I)“]

Una forma de explorar un espacio tan grande como es el de trayectorias en el plano en busca de un contraejemplo es restringirse a un subconjunto pequeño del mismo. Para este caso podemos elegir las trayectorias poligonales formadas por tres segmentos (con la idea de ampliar el número de segmentos en caso de no ser posible encontrar un contraejemplo). Expresándolo más formalmente, equivaldría a elegir una función de control $\theta(t)$ de la forma

$\theta (t) = \theta_1 H(t - t_1) + (\theta_2 - \theta_1) H(t - t_2)$ ,

siendo $H(t)$ el escalón unitario y siendo $t_1$ , $\theta_1$ , $t_2$ y $\theta_2$ los parámetros de la trayectoria. Para no arrastrar $T$ por todos lados, podemos tomar $T = 1$ .

Obviamente estas trayectorias no cumplen el requisito de tener derivadas finitas, ya que tienen esquinas en $t = t_1$ y $t = t_2$ . Pero si se encuentra una una solución para una de estas trayectorias poligonales es intuitivamente plausible que pueda luego ser “redondeada” para conseguir derivadas finitas.

Esta familia de trayectorias cumple automáticamente con el requisito de que $\theta(0) = 0$ , así que solo resta expresar las otras dos ecuaciones en términos de los parámetros. Empezando con la restricción correspondiente a la trayectoria con velocidad unitaria, tenemos

$\int_0^1 e^{-i\theta_(t)} dt = \int_0^{t_1} e^0 dt + \int_{t_1}^{t_2} e^{-i\theta_1} + \int_{t_2}^1 e^{-i\theta_2}dt = 0$ .

Como son integrales de constantes, se simplifican a la siguiente expresión:

$t_1 + (t_2 - t_1) e^{i\theta_1} + (1 - t_2) e^{i\theta_2} = 0$ .

La restricción correspondiente a la trayectoria con aceleración unitaria será solo algo más compleja:

$\int_0^1 t e^{-i\theta (t)} dt = \int_0^{t_1} t e^0 dt + \int_{t_1}^{t_2} t e^{-i\theta_1} dt + \int_{t_2}^1 t e^{-i\theta_2} dt = 0$

$\int_0^{t_1} t dt + e^{-i\theta_1}\int_{t_1}^{t_2} t dt + e^{-i\theta_2}\int_{t_2}^1 t dt = 0$

$\left(\frac{t_1^2}{2}-\frac{0^2}{2}\right) + e^{-i\theta_1}\left(\frac{t_2^2}{2}-\frac{t_1^2}{2}\right) + e^{-i\theta_2}\left(\frac{1^2}{2}-\frac{t_2^2}{2}\right) = 0$

$t_1^2 + e^{-i\theta_1}\left(t_2^2 - t_1^2\right) + e^{-i\theta_2}\left(1 - t_2^2\right) = 0$ .

Como toda exponencial de un número puramente imaginario puede caracterizarse como un número complejo de módulo unitario, podemos reemplazar las exponenciales por nuevas variables con restricciones asociadas. Esto dejaría la búsqueda de trayectorias que cumplan las ecuaciones planteadas originalmente reducida a la resolución del siguiente sistema de ecuaciones:

$t_1 + w_1(t_2 - t_1) + w_2(1 - t_2) = 0$

$t_1^2 + w_1(t_2^2 - t_1^2) + w_2(1 - t_2^2) = 0$

$|w_1| = 1$

$|w_2| = 1$ .

Separando en componentes reales e imaginarias, el sistema puede convertirse en uno puramente algebraico (a costa de aumentar el número de ecuaciones):

$t_1 + x_1(t_2 - t_1) + x_2(1 - t_2) = 0$

$y_1(t_2 - t_1) + y_2(1 - t_2) = 0$

$t_1^2 + x_1(t_2^2 - t_1^2) + x_2(1 - t_2^2) = 0$

$y_1(t_2^2 - t_1^2) + y_2(1 - t_2^2) = 0$

$x_1^2 + y_1^2 = 1$

$x_2^2 + y_2^2 = 1$ .

Este sistema algebraico, junto con las condiciones de orden temporal y no degeneración $0 < t_1 < t_2 < 1$ , puede ser resuelto en forma manual o con ayuda de una computadora. Se obtiene como resultado la siguiente solución única:

$t_1 = \frac{1}{4}$

$x_1 = -1$

$y_1 = 0$

$t_2 = \frac{3}{4}$

$x_2 = 1$

$y_2 = 0$ .

Como $y_1$ e $y_2$ son nulos, puede verse que ambas trayectorias (con velocidad uniforme y con aceleración uniforme) se desarrollarán en línea recta. Ya que, consiguientemente, un gráfico espacial no resultaría muy informativo, podemos presentar ambas trayectorias en un gráfico espacio-temporal:

Diagrama espacio-temporal de las trayectorias recorridas con velocidad y con aceleración unitarias

Si bien esta función de control (única excepto por las ambigüedades propias de trabajar con ángulos)

$\theta(t) = \pi H(t - \frac{1}{4}) + \pi H(t - \frac{3}{4})$

satisface las tres ecuaciones con las que comenzamos el análisis en el post anterior, no puede cumplir la condición de finitud en las derivadas tal como mencionamos anteriormente. En el próximo post veremos como “redondear” la trayectoria sin que deje de cumplir las ecuaciones requeridas.

Spin Foam

Just another WordPress.com weblog

Monthly Archives: February 2009

Equidistancia en R^n (parte II)

Equidistancia en R^n (parte I)

Un problema de integrales (III)

Un problema de integrales (II)