From Wikipedia, the free encyclopedia
La corba de Lebesgue és una corba fractal contínua que recobreix el pla i és derivable gairebé a tots els punts, introduïda per Henri Lebesgue l'any 1905.[1] També s'anomena corba de Morton per Guy Macdonald Morton,[2] el primer informàtic de dades que va fer-la servir per emmagatzemar dades de forma seqüencial, com a mapatge de dades multidimensionals a una única dimensió preservant la localitat dels punts de dades propers.[3] Aquest mapatge és efectiu perquè la corba correspon al valor z d'un punt multidimensional, és a dir, una estructura intercalada de les representacions binàries dels seus valors de coordenades; per aquest motiu també se l'anomena corba d'ordre z. Un cop ordenades les dades en aquest ordre, es pot utilitzar qualsevol estructura de dades unidimensionals, com ara arbres de cerca binària, arbres B, skip lists o taules hash. L'ordenació resultant es pot descriure de manera equivalent com l'ordre que s'obtindria d'un primer recorregut de profunditat d'un quadtree.
La corba es pot obtenir dividint un pla en quatre quadrants i unint els punts centrals de cada quadrant d'esquerra a dreta i de dalt a baix ordenadament, formant una Z. Per obtenir la corba d'ordre següent, es divideix de nou cadascun dels quadrants en quatre parts i s'hi aplica el mateix procediment, i finalment s'uneix el punt final de la Z de cada quadrant amb l'inicial del següent. Per tant, el nombre de punts per un ordre n és 4n. Aquesta construcció evidencia que la corba és autosimilar respecte l'ordre anterior, excepte les línies d'unió entre els quadrants principals.
Corba de Lebesgue tridimensional | ||
---|---|---|
![]() |
![]() |
![]() |
La corba es pot generalitzar per dimensions superiors aplicant el mateix procediment. En el cas de tres dimensions, a cada pas es divideix cada cub en 8 cubs i se n'uneixen els punts centrals en ordre binari.[4]
Analíticament, la corba està relacionada amb el conjunt de Cantor i la funció esglaonada. Els nombres del conjunt de Cantor admeten una expansió ternària per tal de ser mapats en un quadrat de forma que per cada valor hi ha una a la qual correspon aquesta .
Aquesta propietat implica que en el mapatge , les dues coordenades de qualsevol punt al quadrat de la unitat admeten una expansió binària; les dues es poden entrellaçar en un sol membre de en un revers de la definició de .
Lebesgue va ampliar el mapatge de amb una interpolació lineal de a per construir la funció esglaonada de Cantor. Definint com un dels intervals eliminats en la construcció del conjunt de Cantor, llavors per :
La funció és diferenciable a tot interval , i com que la mesura ("llargada") del conjunt és 0, és diferenciable gairebé a tot l'interval unitari .