Curva de Hilbert

Curva que llena el espacio

Primeras seis iteraciones de la 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 . ${\displaystyle n}$ ${\displaystyle \textstyle 2^{n}-{1 \over 2^{n}}}$ ${\displaystyle n}$ ${\displaystyle 1}$

Imágenes

• 
  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]

Aplicaciones y algoritmos de mapeo

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]}

Representación como sistema de Lindenmayer

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

Curva de Hilbert en su sexta iteración

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.

Otras implementaciones

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.

Véase también

• 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

Notas

1. D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.
2. G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157-160.
3. Bourges, Pascale. "Capítulo 1: fractales", Fractales et caos . Consultado: 9 de febrero de 2019.
4. Moon, B.; Jagadish, H. V.; Faloutsos, C.; Saltz, J. H. (2001), "Análisis de las propiedades de agrupamiento de la curva de llenado del espacio de Hilbert", IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124–141, CiteSeerX  10.1.1.552.6697 , doi :10.1109/69.908985, S2CID  728511.
5. "Mapeo de toda Internet con curvas de Hilbert". blog.benjojo.co.uk . Consultado el 2 de enero de 2021 .
6. Spires, Shannon V.; Goldsmith, Steven Y. (1998), Drogoul, Alexis; Tambe, Milind; Fukuda, Toshio (eds.), "Búsqueda geográfica exhaustiva con robots móviles a lo largo de curvas que llenan el espacio", Collective Robotics , vol. 1456, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 1–12, doi :10.1007/bfb0033369, ISBN 978-3-540-64768-3, consultado el 14 de agosto de 2023
7. Sadat, Seyed Abbas; Wawerla, Jens; Vaughan, Richard (2015). Trayectorias fractales para cobertura aérea no uniforme en línea . Conferencia internacional IEEE sobre robótica y automatización (ICRA) de 2015. págs. 2971–2976.
8. Thiadmer Riemersma (1 de diciembre de 1998). "Una técnica de tramado equilibrado". Diario del usuario de C/C++ . Dr. Dobb's.
9. I. Kamel, C. Faloutsos, Hilbert R-tree: Un árbol R mejorado usando fractales, en: Actas de la 20.ª Conferencia Internacional sobre Bases de Datos Muy Grandes, Morgan Kaufmann Publishers Inc., San Francisco, CA, EE. UU., 1994, págs. 500–509.
10. Eavis, T.; Cueva, D. (2007). "Una arquitectura de compresión espacial de Hilbert para entornos de almacenamiento de datos". Almacenamiento de datos y descubrimiento de conocimiento . Apuntes de clase en informática. Vol. 4654. págs. 1–12. doi :10.1007/978-3-540-74553-2_1. ISBN 978-3-540-74552-5.
11. Lemire, Daniel; Kaser, Owen (2011). "Reordenamiento de columnas para índices más pequeños". Ciencias de la información . 181 (12): 2550–2570. arXiv : 0909.1346 . doi :10.1016/j.ins.2011.02.002. S2CID  15253857.
12. Programación de la curva de Hilbert por John Skilling
13. Grant Tebbin: Cálculo de las coordenadas de la curva de Hilbert
14. Hamilton, CH; Rau-Chaplin, A. (2007). "Índices de Hilbert compactos: curvas que llenan el espacio para dominios con longitudes de lados desiguales". Information Processing Letters . 105 (5): 155–163. doi :10.1016/j.ipl.2007.08.034.
15. Alber, J.; Niedermeier, R. (2000). "Sobre curvas multidimensionales con propiedad de Hilbert". Teoría de sistemas informáticos . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . doi :10.1007/s002240010003. S2CID  788382. 
16. HJ Haverkort, F. van Walderveen, Curvas de Hilbert de cuatro dimensiones para árboles R, en: Actas del undécimo taller sobre ingeniería de algoritmos y experimentos, 2009, págs. 63–73.
17. Voorhies, Douglas: Curvas que llenan el espacio y una medida de coherencia, págs. 26-30, Graphics Gems II.

Lectura adicional

• 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.

Enlaces externos

• 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)