curva de Hilbert

Curva de llenado de espacio

Primeras seis iteraciones de la 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, ^{[1] como una variante de las} curvas de Peano de relleno de espacio descubiertas por Giuseppe Peano. en 1890. ^[2]

Debido a que llena 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áfica es un conjunto compacto homeomorfo al intervalo unitario cerrado, con dimensión de Hausdorff 2) .

La curva de Hilbert se construye como límite de curvas lineales por tramos . La longitud de la enésima curva 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.
• 
  Reglas de producción
• 
  Curva de Hilbert, construcción codificada por colores
• 
  Una curva de Hilbert tridimensional con colores que muestran la progresión.
• 
  Variante, primeras tres iteraciones ^[3]

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. ^[4] 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. ^[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 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. ^[8] Las curvas de Hilbert en dimensiones superiores son un ejemplo de una generalización de los códigos 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 ^[9] (ver Árbol R de Hilbert ). También se han utilizado para ayudar a comprimir almacenes de datos. ^{[10] [11]}

La distancia lineal de cualquier punto a lo largo de la curva se puede convertir en 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 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 "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 ^[17] analiza la coherencia de la curva de Hilbert y proporciona su implementación.

La curva de Hilbert se usa comúnmente para renderizar imágenes o videos. Los programas comunes como Blender y Cinema 4D utilizan la curva de Hilbert para trazar los objetos y renderizar la escena. ^{[ cita necesaria ]}

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.

Ver también

• Programación de la curva de Hilbert
• Hilbert R-árbol
• Localidad de referencia
• Hashing sensible a la localidad
• curva de Moore
• Polígono de Murray
• Curva de Sierpiński
• Lista de fractales por 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. Luna, B.; Jagadish, HV; Faloutsos, C.; Saltz, JH (2001), "Análisis de las propiedades de agrupamiento de la curva de llenado de 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 todo Internet con curvas de Hilbert". blog.benjojo.co.uk . Consultado el 2 de enero de 2021 .
6. Agujas, 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 de llenado de 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, recuperado 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" . 2015 Conferencia Internacional IEEE sobre Robótica y Automatización (ICRA). págs. 2971–2976.
8. Thiadmer Riemersma (1 de diciembre de 1998). "Una técnica de tramado equilibrado". Diario del usuario de C/C++ . Del doctor Dobb.
9. I. Kamel, C. Faloutsos, Hilbert R-tree: Un árbol R mejorado que utiliza fractales, en: Actas de la vigésima 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 conocimientos . Apuntes de conferencias sobre 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). "Reordenación 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 compactos de Hilbert: curvas que llenan el espacio para dominios con longitudes de lados desiguales". Cartas de procesamiento de información . 105 (5): 155-163. doi :10.1016/j.ipl.2007.08.034.
15. Alberto, J.; Niedermeier, R. (2000). "Sobre curvas multidimensionales con la propiedad de Hilbert". Teoría de los Sistemas Computacionales . 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 experimentos e ingeniería de algoritmos, 2009, págs.
17. Voorhies, Douglas: Curvas que llenan el espacio y una medida de coherencia, págs. 26-30, Graphics Gems II.

Otras lecturas

• Warren Jr., Henry S. (2013). El placer del hacker (2 ed.). 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. Matemáticas Estética, Inc. ISBN 978-1-7332188-0-1.

enlaces externos

• Curva de Hilbert dinámica con JSXGraph
• Demostración de la curva de Hilbert 3D de Three.js WebGL
• Caricatura XKCD que utiliza las propiedades de localidad de la curva de Hilbert para crear un "mapa de Internet"
• Generador de Gcode para la curva de Hilbert
• Algoritmo iterativo para dibujar la curva de Hilbert en JavaScript
• Algoritmo 781: generación de la curva de llenado de espacio de Hilbert mediante recursividad (Biblioteca digital ACM)