Corba de Hilbert

La corba de Hilbert és una corba fractal contínua que recobreix el pla, descrita inicialment pel matemàtic alemany David Hilbert l'any 1891^[1] com una variant de les corbes que recobreixen el pla descrites per Giuseppe Peano el 1890.^[2]

Corba de Hilbert. A l'exemple es mostren els ordres 1 fins al 8. La corda va canviant de color progressivament de manera que indica l'ordre pel que passa per cada quadrant, representant per tant la distància recorreguda.

La corba de Hilbert és auto-similar; cada secció d'un determinat ordre correspon a la corba en l'ordre anterior. Com que tendeix al recobriment de tot el pla, la seva dimensió de Hausdorff-Bezikóvitx és 2.

Procediment

Podem descriure la corba com una corda contínua sobre un pla dividit en graelles, que va d'una a l'altra ordenadament sense deixar-se'n cap.

Ordre 1 - Graella de 2 x 2 cel·les, recobert en forma de U; superior-esquerra, inferior-esquerra, inferior-dreta, superior-dreta.

Ordre 2 - Graella de 4 x 4 cel·les, on es dibuixa l'ordre anterior seguint el mateix ordre, però girant la superior-esquerra 90° en sentit antihorari i la superior-dreta 90° en sentit horari, de manera que els extrems de la corda quedin sempre propers, és a dir en cel·les adjacents. S'uneixen aquests extrems obtenint de nou una corba contínua.

Ordres posteriors - Es torna a fer el mateix procediment partint de l'ordre anterior.

Procediment de formació de la corba de Hilbert, primers ordres

Propietats

Els talls amb molta diferència de distància recorreguda entre punts adjacents (a la representació, canvis de color sobtats) coincideixen amb els marges de les cel·les.

Gràfic de distàncies sobre els punts d'una corba de Hilbert d'ordre 4. Eix X: Distància recorreguda (d), Eix Y: distància de Pitàgores entre un punt (origen) i la resta de punts. Es marca amb una línea vertical el punt origen actual.

Mapa de calor que mostra la distància entre tots els parells de valors de d a una corba de Hilbert d'ordre 4. Quant més brillant, major distància. La part fosca tendeix a concentrar-se a prop de la diagonal.

Com que la corda serpenteja de forma contínua per tota la graella, té una propietat interessant: Si es converteix en cada punt la distància recorreguda per la corda (d) a un parell de coordenades de la graella (x, y), altres distàncies properes també tenen coordenades properes. Es pot formar així una funció de mapeig entre una i dues dimensions que preserva bé la localitat, és a dir, punts propers en una dimensió també són propers després de fer la conversió a dues dimensions.^[3] Ara bé, la funció inversa no sempre pot ser certa; coordenades similars tenen distàncies molt diferents si es creuen els marges de les cel·les.

Si es fa un gràfic de distàncies del punts de la corba, s'observa que els punts amb una d similar tenen una distància baixa al pla, mentre que a mesura que t'allunyes de d, tendeix a ser més alta. La mateixa idea també es pot representar amb un mapa de calor de la distància entre tots els parells de valors de d.

Una altra propietat interessant de la corba és que si es defineix p com la proporció de corda recorreguda en un punt concret, punts amb la mateixa p en diferents ordres tendeixen a focalitzar-se en un punt concret del pla. Això és fàcilment observable en la representació per colors de la distància recorreguda; al augmentar l'ordre els colors es mantenen al mateix lloc de forma cada cop més precisa.^[4]

Les característiques de la corba de Hilbert es poden generalitzar per més dimensions.^[5][6] A més, és possible implementar corbes de Hilbert eficientment fins i tot quan l'espai de les dades no forma un quadrat.^[7]

Usos pràctics

Les corbes de Hilbert poden ajudar a crear índexs de bases de dades espacials; quan se cerca un registre en una ubicació geogràfica propera, pot ser útil per determinar la prioritat per explorar. Per exemple, el rang d'adreces IP utilitzat per ordinadors pot ser mapejat a una imatge utilitzant la corba de Hilbert, de manera que adreces similars es mostren properes entre elles a la imatge.

També s'utilitza en processament d'imatges, per optimitzar el dithering al reduir la paleta d'una imatge o bé passar-la a escala de grisos.

Corbes de Hilbert de més dimensions es poden utilitzar per implementar la planificació de tasques en aplicacions informàtiques de processament paral·lel; converteix l'assignació de tasques multidimensional en un espai unidimensional i assigna tasques relacionades a ubicacions amb nivells de proximitat més alts.^[5]

Generalització per dimensions superiors

Corba de Hilbert tridimensional, el canvi de color mostra la progressió

Hilbert no va descriure com generalitzar la corba a tres dimensions o més, i hi ha diverses maneres d'aplicar les transformacions en l'eix addicional a l'algorisme. Si es tenen en compte només les propietats bàsiques descrites per la segona dimensió, és a dir que sigui auto-similar, contínua i basada en octets, hi ha 10.694.807 corbes de Hilbert equivalents en tres dimensions.^[8] Es pot reduir aquest nombre segons si es busca que tinguin algunes propietats addicionals presents en la versió bidimensional, però malauradament no n'hi ha cap que les compleixi totes.^[8]

Vegeu també

• Corba de Peano
• Corba de Moore

Referències

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. Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. «Analysis of the clustering properties of the Hilbert space-filling curve». IEEE Transactions on Knowledge and Data Engineering, 13, 1, 2001, p. 124–141. DOI: 10.1109/69.908985.
4. Irving, Geoffrey; Segerman, Henry «Developing Fractal Curves». Math Ok State. amb enllaç a Impressió 3D de la corba de Hilbert en 3 dimensions (anglès) [Consulta: 18 març 2020]
5. Alber, J.; Niedermeier, R. «On multidimensional curves with Hilbert property». Theory of Computing Systems, 33, 4, 2000, pàg. 295–312. DOI: 10.1007/s002240010003.
6. H. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
7. Hamilton, C. H.; Rau-Chaplin, A. «Compact Hilbert indices: Space-filling curves for domains with unequal side lengths». Information Processing Letters, 105, 5, 2007, pàg. 155–163. DOI: 10.1016/j.ipl.2007.08.034.
8. Haverkort, Herman «How many three-dimensional Hilbert curves are there?». Eindhoven University of Technology, 2016, pàg. 45-6.

Enllaços externs

• Iterative algorithm for drawing Hilbert curve (anglès)