Curva de Hilbert

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

Por ocupar todo el 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áfico es un conjunto compacto homeomorfo al intervalo unitario cerrado, con dimensión de Hausdorff 1).

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

• 
  Curva de Hilbert, primer orden
• 
  Curvas de Hilbert, primer y segundo orden
• 
  Curvas de Hilbert, de primer a tercer orden
• 
  Normas de producción
• 
  Curva de Hilbert, construcción codificada por colores
• 
  Una curva de Hilbert en 3D con color que muestra la progresión.
• 
  Variante, primeras tres iteraciones ^[3]

Tanto la curva de Hilbert verdadera como sus aproximaciones discretas son útiles porque proporcionan una correspondencia entre el espacio unidimensional y el bidimensional que preserva bastante bien la localidad. ^[4] Esto significa que dos puntos de datos que están cerca uno del otro en el espacio unidimensional también están cerca uno del otro después del plegado. La inversa no siempre puede ser cierta.

Debido a esta propiedad de localidad, la curva de Hilbert se utiliza 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 representaría de 2D a 1D para encontrar el color de cada píxel, y la curva de Hilbert se utiliza a veces porque mantiene las direcciones IP cercanas unas a otras en la imagen. ^[5] 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. ^{[6] [7]}

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 el uso de un umbral, con la cantidad sobrante de cada píxel añadida 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 se utiliza a veces porque no crea los patrones que distraen que serían visibles para el ojo si el orden fuera simplemente de izquierda a derecha en cada fila de píxeles. ^[8] 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 fines 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 de árboles R ^[9] (véase Árbol R de Hilbert ). También se han utilizado para ayudar a comprimir los almacenes de datos. ^{[10] [11]}

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. ^{[12] [13]}

Es posible implementar curvas de Hilbert de manera eficiente incluso cuando el espacio de datos no forma un cuadrado. ^[14] Además, existen varias generalizaciones posibles de las curvas de Hilbert a dimensiones superiores. ^{[15] [16]}

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

Alfabeto  : A, B

Constantes  : F + −

Axioma  : A

Reglas de producción :

A → +BF−AFA−FB+

B → −AF+BFB+FA−

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

Graphics Gems II ^{[17] [ ¿promoción? ]} analiza la coherencia de la curva de Hilbert y proporciona su implementación.

La curva de Hilbert se utiliza habitualmente para renderizar imágenes o vídeos. Programas habituales como Blender y Cinema 4D utilizan la curva de Hilbert para trazar los objetos y renderizar la escena. ^{[ cita requerida ]}

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

Wikimedia Commons tiene medios relacionados con Curva de Hilbert.

• Programación de curvas de Hilbert
• Árbol R de Hilbert
• Localidad de referencia
• Hashing sensible a la localidad
• Curva de Moore
• Polígono Murray
• Curva de Sierpinski
• Lista de fractales según la dimensión de Hausdorff

• Warren Jr., Henry S. (2013). Hacker's Delight (2.ª edición). Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8.
• McKenna, Douglas M. (2019). Curvas de Hilbert: de afuera hacia adentro y de adentro hacia afuera. Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1.

• Curva de Hilbert dinámica con JSXGraph
• Demostración de curva de Hilbert 3D WebGL de Three.js
• Dibujo animado de XKCD que utiliza las propiedades de localidad de la curva de Hilbert para crear un "mapa de Internet"
• Generador de Gcode para curvas de Hilbert Archivado el 9 de julio de 2019 en Wayback Machine
• Algoritmo iterativo para dibujar la curva de Hilbert en JavaScript
• Algoritmo 781: generación de la curva de Hilbert que llena el espacio mediante recursión (Biblioteca Digital ACM)