Curva de Hilbert

La curva de Hilbert (también conocida como curva de relleno de espacio de Hilbert) es una curva de relleno de espacio fractal continua descrita por primera vez por el matemático alemán David Hilbert en 1891. como una variante de las curvas de Peano que llenan el espacio descubiertas por Giuseppe Peano en 1890.

Porque llena espacio, su dimensión de Hausdorff es 2 (precisamente, su imagen es el cuadrado unitario, cuya dimensión es 2 en cualquier definición de dimensión; su gráfica es un conjunto compacto homeomorfo al intervalo unitario cerrado, con Hausdorff dimensión 2).

La curva de Hilbert se construye como un límite de curvas lineales empotradas. La longitud de la ${\displaystyle n}$la curva ${\displaystyle \textstyle 2^{n}-{1\over 2^{n}}$, es decir, la longitud crece exponencialmente con ${\displaystyle n}$, aunque cada curva está contenida en un cuadrado con área ${\displaystyle 1}$.

Imágenes

• 
  Hilbert curva, primer orden
• 
  Curvas Hilbert, órdenes primera y segunda
• 
  Curvas Hilbert, primero a terceras órdenes
• 
  Normas de producción
• 
  curva Hilbert, construcción codificada en color
• 
  Una curva de Hilbert 3-D con progresión de color
• 
  Variante, primeras tres iteraciones

Aplicaciones y algoritmos de mapeo

Tanto la verdadera curva de Hilbert como sus aproximaciones discretas son útiles porque brindan un mapeo entre el espacio 1D y 2D que preserva bastante bien la localidad. Esto significa que dos puntos de datos que están cerca uno del otro en un espacio unidimensional también lo están después del plegado. Lo contrario no siempre puede ser cierto.

Debido a esta propiedad de localidad, la curva de Hilbert se usa ampliamente en informática. Por ejemplo, el rango de direcciones IP utilizadas por las computadoras se puede representar en una imagen utilizando la curva de Hilbert. El código para generar la imagen se asignaría de 2D a 1D para encontrar el color de cada píxel, y a veces se utiliza la curva de Hilbert porque mantiene las direcciones IP cercanas unas de otras en la imagen. La propiedad de localidad de la curva de Hilbert también se ha utilizado para diseñar algoritmos para explorar regiones con robots móviles.

En un algoritmo llamado tramado de Riemersma, las fotografías en escala de grises se pueden convertir en una imagen en blanco y negro tramada mediante umbralización, y la cantidad sobrante de cada píxel se agrega al siguiente píxel a lo largo de la curva de Hilbert. El código para hacer esto se asignaría de 1D a 2D, y la curva de Hilbert a veces se usa porque no crea los patrones que distraen y que serían visibles a simple vista si el orden fuera simplemente de izquierda a derecha en cada fila de píxeles. Las curvas de Hilbert en dimensiones superiores son un ejemplo de una generalización de los códigos de Gray y, a veces, se utilizan para propósitos similares, por razones similares. Para bases de datos multidimensionales, se ha propuesto utilizar el orden de Hilbert en lugar del orden Z porque tiene un mejor comportamiento de conservación de la localidad. Por ejemplo, las curvas de Hilbert se han utilizado para comprimir y acelerar los índices del árbol R (ver Árbol R de Hilbert). También se han utilizado para ayudar a comprimir almacenes de datos.

La distancia lineal de cualquier punto a lo largo de la curva se puede convertir a coordenadas en n dimensiones para un n dado, y viceversa, utilizando cualquiera de varias técnicas matemáticas estándar, como el método de Skilling.

Es posible implementar curvas de Hilbert de manera eficiente incluso cuando el espacio de datos no forma un cuadrado. Además, existen varias generalizaciones posibles de las curvas de Hilbert a dimensiones superiores.

Representación como sistema Lindenmayer

La curva de Hilbert se puede expresar mediante un sistema de reescritura (sistema L).

AlfabetoA, B

Constantes: F + −

AxiomA

Normas de producción:

A → +BF−AFA−FB+

B → −AF+BFB+FA−

Aquí, "F" significa "avanzar", "+" significa "girar a la izquierda 90°", "-" significa "girar a la derecha 90°" (ver gráficos de tortugas) y "A" y "B" se ignoran durante el dibujo.

Otras implementaciones

Graphics Gems II analiza la coherencia de la curva de Hilbert y proporciona su implementación.

La curva de Hilbert se utiliza comúnmente para renderizar imágenes o vídeos. Los programas comunes como Blender y Cinema 4D utilizan la curva de Hilbert para trazar los objetos y renderizar la escena.

El software de corte utilizado para convertir modelos 3D en trayectorias de herramientas para una impresora 3D normalmente tiene la curva de Hilbert como opción para un patrón de relleno.