Curva de Hilbert

La curva de Hilbert es una curva continua que llena un cuadrado . Fue descrito por primera vez por el matemático alemán David Hilbert en 1891 .

Dado que cubre un cuadrado, su dimensión de Hausdorff y su dimensión topológica son iguales a 2. Sin embargo, se considera parte de los fractales .

La longitud euclidiana de H n (la curva aproximada continua obtenida en la n -ésima iteración) es  ; por tanto, crece exponencialmente con n . 2no-12no{\ Displaystyle 2 ^ {n} - {1 \ over 2 ^ {n}}}

Para navegar en bases de datos multidimensionales, se propuso la curva de Hilbert en lugar de la curva de Lebesgue porque tiene un comportamiento que preserva mejor la localidad.

Construcción geométrica

Hilbert define la función como un límite de funciones dando las aproximaciones sucesivas de la curva de Hilbert. F:[0,1]→[0,1]2{\ Displaystyle f: [0,1] \ a [0,1] ^ {2}}Fno:[0,1]→[0,1]2{\ Displaystyle f_ {n}: [0,1] \ a [0,1] ^ {2}}

• En el paso 0, el gráfico H 0 se limita a un solo punto, dispuesto en el centro del cuadrado . Este punto es tanto el punto de partida como el punto final de H 0 . El centro del cuadrado de coordenadas (1/2, 1/2) es la imagen por una función f 0 de todo el intervalo .[0,1]×[0,1]{\ Displaystyle [0.1] \ times [0.1]}[0,1]{\ Displaystyle [0,1]}
• En el paso 1, cortamos el intervalo en cuatro partes iguales y hacemos que cada intervalo de la subdivisión corresponda a un cuarto del cuadrado inicial. Más precisamente, el intervalo está asociado con el subcuadrado  ; el intervalo está asociado con el subcuadrado  ; el intervalo está asociado con el subcuadrado  ; y finalmente, el intervalo se asocia con el subcuadrado . Así, el curso de los cuatro subcuadrados se realiza en el siguiente orden:[0,1]{\ Displaystyle [0,1]}[0,1/4]{\ displaystyle [0,1 / 4]}[0,1/2]×[0,1/2]{\ Displaystyle [0.1 / 2] \ times [0.1 / 2]}[1/4,1/2]{\ Displaystyle [1 / 4,1 / 2]}[0,1/2]×[1/2,1]{\ Displaystyle [0,1 / 2] \ times [1 / 2,1]}[1/2,3/4]{\ Displaystyle [1 / 2,3 / 4]}[1/2,1]×[1/2,1]{\ displaystyle [1 / 2,1] \ times [1 / 2,1]}[3/4,1]{\ Displaystyle [3 / 4,1]}[1/2,1]×[0,1/2]{\ displaystyle [1 / 2,1] \ times [0,1 / 2]}

1	2
0	3

Si conectamos los centros de estos cuadrados por segmentos, obtenemos la gráfica H 1 . Su punto inicial es el punto de coordenadas y su punto final es el punto de coordenadas . Es el arco parametrizado por una función f 1 que envía el intervalo [0, 1/4] de la parte de H 1 contenida en el cuadrado 0, el intervalo de la parte de H 1 contenida en el cuadrado 1, el intervalo de la parte de H 1 contenido en el cuadrado 2, y el intervalo de la parte de H 1 contenido en el cuadrado 3, siguiendo la dirección de desplazamiento.(1/4,1/4){\ Displaystyle (1 / 4,1 / 4)}(3/4,1/4){\ Displaystyle (3 / 4,1 / 4)}[1/4,1/2]{\ Displaystyle [1 / 4,1 / 2]}[1/2,3/4]{\ Displaystyle [1 / 2,3 / 4]}[3/4,1]{\ Displaystyle [3 / 4,1]}

• En el paso n , cada intervalo de la subdivisión obtenido en el paso n -1 se divide en cuatro, al igual que el cuadrado asociado con él. Tenemos en cada cuadrado de lado 1/2 numerado de 0 a 3 un ejemplo del gráfico H n -1 calculado en la fila anterior, después de haberlo sometido a una homotetía de razón 1/2, pero de modo que, para i variando de 0 a 2, el punto final del gráfico H n -1 colocado en el cuadrado i está lo más cerca posible del punto inicial del gráfico H n -1 colocado en el cuadrado i +1. Para ello, basta con realizar una simetría con respecto a la diagonal ascendente en el cuadrado numerado 0, y una simetría con respecto a la diagonal descendente en el cuadrado numerado 3. Así, en el paso n = 2, la dirección de desplazamiento en cada subcuadrado del paso 1 es el siguiente:

1	2	1	2
0	3	0	3
3	2	1	0
0	1	2	3

El punto inicial del gráfico H n así obtenido es el punto inicial del gráfico H n -1 del cuadrado 0 en la parte inferior izquierda, y el punto final del gráfico H n es el punto final del gráfico H n -1 de cuadrado 3, en la parte inferior derecha. Las partes de H n contenidas en cada uno de los 4 n cuadrados pequeños del lado 1/2 n en orden de recorrido son las imágenes sucesivas por la función f n de cada uno de los intervalos sucesivos de longitud 1/4 n subdivididos .[0,1]{\ Displaystyle [0,1]}

Debido a la definición local de las gráficas H n , la secuencia de funciones continuas ( f n ) es uniformemente Cauchy , por lo tanto converge uniformemente a una función continua f cuya gráfica es la curva de Hilbert. Este gráfico es denso en el cuadrado . Además, es compacto como una imagen continua del compacto [0,1], por lo que es un denso cerrado de , por lo tanto es igual a . f es un mapa sobreyectivo. No es derivable en ningún momento. [0,1]×[0,1]{\ Displaystyle [0.1] \ times [0.1]}[0,1]×[0,1]{\ Displaystyle [0.1] \ times [0.1]}[0,1]×[0,1]{\ Displaystyle [0.1] \ times [0.1]}

Podemos demostrar por inducción que las gráficas H n , y por tanto la curva de Hilbert al cruzar el límite, son simétricas con respecto a la recta de la ecuación x = 1/2.

Definición recursiva

La parametrización f ( t ) = ( x ( t ), y ( t )) de la función de Hilbert previamente definida satisface, teniendo en cuenta las simetrías de la construcción:

para t∈[0,1/4],X(t)=y(4t)2,y(t)=X(4t)2{\ Displaystyle t \ in [0,1 / 4], x (t) = {\ frac {y (4t)} {2}}, y (t) = {\ frac {x (4t)} {2} }} para t∈[1/4,1/2],X(t)=X(4t-1)2,y(t)=1+y(4t-1)2{\ Displaystyle t \ in [1 / 4,1 / 2], x (t) = {\ frac {x (4t-1)} {2}}, y (t) = {\ frac {1 + y ( 4t-1)} {2}}} para t∈[1/2,3/4],X(t)=1+X(4t-2)2,y(t)=1+y(4t-2)2{\ Displaystyle t \ in [1 / 2,3 / 4], x (t) = {\ frac {1 + x (4t-2)} {2}}, y (t) = {\ frac {1+ y (4t-2)} {2}}} para t∈[3/4,1],X(t)=2-y(4t-3)2,y(t)=1-X(4t-3)2{\ Displaystyle t \ in [3 / 4,1], x (t) = {\ frac {2-y (4t-3)} {2}}, y (t) = {\ frac {1-x ( 4t-3)} {2}}}

También f ( 0 ) = (0, 0) yf ( 1 ) = (1, 0).

También podemos traducir estas relaciones de la siguiente manera. Planteemos:

S 0 la simetría con respecto a la recta y = x S 1 la traslación del vector (0, 1) S 2 la traslación del vector (1,1) S 3 la simetría con respecto a la recta y = - x , compuesta con la traslación del vector (2,1).

Entonces, si donde u n son los 4 dígitos base de t , tenemos: t=0,tu1tu2⋯tuno⋯=∑no=0∞tuno4no{\ Displaystyle t = 0, u_ {1} u_ {2} \ cdots u_ {n} \ cdots = \ sum _ {n = 0} ^ {\ infty} {\ frac {u_ {n}} {4 ^ { no}}}}

F(t)=12Stu1(F(0,tu2⋯tuno⋯)){\ Displaystyle f (t) = {\ frac {1} {2}} S_ {u_ {1}} (f (0, u_ {2} \ cdots u_ {n} \ cdots))}

y iterando:

F(t)=12noStu1Stu2⋯Stuno(F(0,tuno⋯)){\ Displaystyle f (t) = {\ frac {1} {2 ^ {n}}} S_ {u_ {1}} S_ {u_ {2}} \ cdots S_ {u_ {n}} (f (0, u_ {n} \ cdots))}

En particular, si t es un real que tiene un número finito n de dígitos en base 4 ( ), tenemos: t=0,tu1tu2⋯tuno{\ Displaystyle t = 0, u_ {1} u_ {2} \ cdots u_ {n}}

F(t)=12noStu1Stu2⋯Stuno(F(0))=12noStu1Stu2⋯Stuno(0,0){\ Displaystyle f (t) = {\ frac {1} {2 ^ {n}}} S_ {u_ {1}} S_ {u_ {2}} \ cdots S_ {u_ {n}} (f (0) ) = {\ frac {1} {2 ^ {n}}} S_ {u_ {1}} S_ {u_ {2}} \ cdots S_ {u_ {n}} (0,0)}

Por tanto, podemos calcular fácilmente el valor de cualquier cantidad y más especialmente el , que dan las coordenadas de los centros de los pequeños cuadrados cuando k varía de 1 a 4 n . F(k4no){\ Displaystyle f ({\ frac {k} {4 ^ {n}}})}F(2k-12×4no)=F(4k-24no+1){\ Displaystyle f ({\ frac {2k-1} {2 \ times 4 ^ {n}}}) = f ({\ frac {4k-2} {4 ^ {n + 1}}})}

Construcción por aproximaciones discretas

Las coordenadas de los vértices del gráfico H n se pueden determinar directamente por inducción . Se llevará a cabo una traslación para que las coordenadas del vértice inicial se devuelvan a (0,0) (y no al centro de un pequeño cuadrado). No obstante, continuaremos denotando este gráfico traducido por H n . Utilizamos para eso una variable auxiliar a indicando la orientación del desplazamiento, pudiendo tomar los valores 0, 1, 2, 3. La orientación dada por a corresponderá a las cuatro siguientes direcciones posibles del gráfico H 1 o de sus simetriza:

También nos damos tres matrices:

X=(0011100111000110),Y=(0110110010010011),A=(3001211012230332)←0=a←1=a←2=a←3=a{\ displaystyle X = {\ begin {pmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \ end {pmatrix} } \ !, \, Y = {\ begin {pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 \ end {pmatrix}} \ !, \; A = {\ begin {pmatrix} 3 & 0 & 0 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 2 & 2 & 3 \\ 0 & 3 & 3 & 2 \ end {pmatrix}} \; \; {\ begin {matrix} {\ begin {array} {ll} \ leftarrow & 0 = a \\\ leftarrow & 1 = a \\\ leftarrow & 2 = a \\ \ leftarrow & 3 = a \ end {matriz}} \ end {matriz}}}

Los índices de fila varían de 0 a 3 (y no de 1 a 4 como es habitual) y estos índices corresponden a valores tomados por a . Los índices de columna también varían de 0 a 3 y corresponden a valores tomados por los dígitos en base 4 de un parámetro t dado. Los elementos de X serán las abscisas y los de Y las ordenadas de un vértice que se busca calcular; los elementos de A darán las distintas orientaciones a seguir durante el cálculo.

En el paso n , la gráfica (traducida de) H n tiene 4 n vértices. Tomados en el orden de navegación, se asociarán con los 4 n elementos t de cuya descomposición en base 4 comprende exactamente n dígitos (posiblemente incluidos los ceros finales): [0,1[{\ Displaystyle [0,1 [}

tno=0.tu1tu2⋯tuno=∑I=1notuI4I{\ Displaystyle t_ {n} = 0.u_ {1} u_ {2} \ cdots u_ {n} = \ sum _ {i = 1} ^ {n} {\ frac {u_ {i}} {4 ^ { I}}}}, .tuI∈{0,1,2,3}{\ Displaystyle u_ {i} \ in \ {0,1,2,3 \}}

Así que dejemos que ese número sea. Las coordenadas del vértice del gráfico H n correspondiente a se pueden calcular por inducción sobre k variando de 0 an , a partir de las coordenadas del vértice del gráfico H k correspondiente al número . Denotemos por las coordenadas de , y sea el valor del parámetro que da la orientación a adoptar para construir los cuatro puntos de la gráfica H k +1 resultantes de (incluyendo el vértice que corresponde a . tno{\ Displaystyle t_ {n}}METROno{\ Displaystyle M_ {n}}tno{\ Displaystyle t_ {n}}METROk{\ Displaystyle M_ {k}}tk=0.tu1tu2⋯tuk{\ Displaystyle t_ {k} = 0.u_ {1} u_ {2} \ cdots u_ {k}}(Xk,yk){\ Displaystyle (x_ {k}, y_ {k})}METROk{\ Displaystyle M_ {k}}ak{\ Displaystyle a_ {k}}METROk{\ Displaystyle M_ {k}}METROk+1{\ Displaystyle M_ {k + 1}}tk+1{\ Displaystyle t_ {k + 1}}

Para k = 0, el gráfico H 0 se reduce al punto (0,0) y la orientación adoptada para construir H 1 corresponde a a = 0. Por lo tanto, inicialmente tenemos:

X0=0,y0=0,a0=0{\ Displaystyle x_ {0} = 0, \, y_ {0} = 0, \, a_ {0} = 0}

Para k que varíe de 1 an , definimos por inducción las secuencias:

Xk=Xk-1+12kXak-1,tuk{\ Displaystyle x_ {k} = x_ {k-1} + {\ frac {1} {2 ^ {k}}} X_ {a_ {k-1}, \, u_ {k}}}

yk=yk-1+12kYak-1,tuk{\ Displaystyle y_ {k} = y_ {k-1} + {\ frac {1} {2 ^ {k}}} Y_ {a_ {k-1}, \, u_ {k}}}

ak=Aak-1,tuk{\ Displaystyle a_ {k} = A_ {a_ {k-1}, \, u_ {k}}}

Efectivamente verificaremos que, si la orientación viene dada por el valor de , entonces las diferencias entre las coordenadas de los cuatro puntos del gráfico H k resultantes y las coordenadas de son, al factor 1/2 k , ubicadas en fila de índice de las matrices X e Y, dependiendo del último dígito de dar el índice de la columna a adoptar. Además, la nueva orientación a adoptar en el punto así obtenido para construir el punto es el número ubicado en la recta índice de la matriz A, nuevamente en función del último dígito de . METROk-1{\ Displaystyle M_ {k-1}}ak-1{\ Displaystyle a_ {k-1}}METROk-1{\ Displaystyle M_ {k-1}}METROk-1{\ Displaystyle M_ {k-1}}ak-1{\ Displaystyle a_ {k-1}}tuk{\ Displaystyle u_ {k}}tk{\ Displaystyle t_ {k}}METROk{\ Displaystyle M_ {k}}METROk+1{\ Displaystyle M_ {k + 1}}ak{\ Displaystyle a_ {k}}ak-1{\ Displaystyle a_ {k-1}}tuk{\ Displaystyle u_ {k}}tk{\ Displaystyle t_ {k}}

Al atravesar los valores de 0.00 ... 0 a 0.33 ... 3 (con n dígitos), los 4 n vértices ocupan la esquina inferior izquierda de los 4 n cuadrados pequeños siguiendo el orden del gráfico H ntno{\ Displaystyle t_ {n}}METROno{\ Displaystyle M_ {n}}

Para obtener los centros de los cuadrados, simplemente agregue a cada coordenada de cada vértice . 12no+1{\ Displaystyle {\ frac {1} {2 ^ {n + 1}}}}METROno{\ Displaystyle M_ {n}}

Generalización en dimensión superior

La curva de Hilbert se puede generalizar a dimensiones superiores. Por ejemplo, en la dimensión 3, en el paso 1, basta con atravesar los ocho vértices del cubo desde un vértice hasta un vértice adyacente. Para ir del paso n -1 al paso n , cortamos el cubo unitario en ocho subcubos en los que tenemos una curva de Hilbert aproximada de orden n -1, pero de modo que el punto final de cada gráfico de orden n -1 sea como lo más cerca posible del vértice inicial del siguiente gráfico de orden n -1.

La generalización también se puede realizar mediante composición funcional. Por tanto, la curva de Hilbert de dimensión 4 puede definirse por f ( t ) = ( x ( x ( t )), y ( x ( t )), x ( y ( t )), y ( y ( t ))). Esta definición puede extenderse a dimensiones que son potencias de 2.

Representación del sistema L

La curva de Hilbert también se puede construir mediante un sistema L  :

Alfabeto  : L, R Constantes  : F, +, - Axioma  : L Reglas  : L → –RF + LFL + FR− R → + LF - RFR - FL +

Aquí, F significa "adelante", + significa "90 ° a la izquierda" y - significa "90 ° a la derecha".

Butz propone un algoritmo para calcular la curva de Hilbert en varias dimensiones.

Referencias

1. (de) D. Hilbert , “  Über die stetige Abbildung einer Linie auf ein Flächenstück  ” , Math. Ana. , vol.  38,1891, p.  459-460 ( leer en línea ).
2. Theodore Bially. Curvas de relleno de espacio: su generación y su aplicación a la reducción del ancho de banda. IEEE Transactions on Information Theory, IT-15 (6): 658–664, 1969. (Citado de Jonathan Lawder: Techniques for Mapping to and from Space-fill Curves , 1999 , p.  58 ).
3. (en) Heinz-Otto Peitgen  (en) y Dietmar Saupe (eds.), La ciencia de las imágenes fractales , Springer ,2012( leer en línea ) , pág.  278.
4. (en) Arthur Butz , "  Algoritmo alternativo para la curva de llenado de espacio de Hilbert  " , IEEE Trans. On Computers , vol.  20,De abril de 1971, p.  424-442.

Ver también

Artículos relacionados

• Curva de Lebesgue
• Curva de Peano
• Lista de fractales por dimensión de Hausdorff

enlaces externos

• (en) Eric W. Weisstein , "  Hilbert Curve  " , en MathWorld
• (es) Curvas de llenado plano al cortar el nudo