Vés al contingut

Corba de Lebesgue

De la Viquipèdia, l'enciclopèdia lliure
Primeres iteracions de la corba de Lebesgue.

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.

Procediment

[modifica]

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.

Generalització per dimensions superiors

[modifica]
Corba de Lebesgue tridimensional
Primer ordre
Segon ordre
Tercer ordre

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]

Relació amb el conjunt de Cantor

[modifica]

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 .

Vegeu també

[modifica]

Referències

[modifica]
  1. Dugundji, James. Topology. Dubuque, Iowa: Wm. C. Brown Publisher, 1989, p. 105. ISBN 0-697-06889-7. 
  2. «Discrete Global Grid Systems Abstract Specification». Open Geospatial Consortium, 2017.
  3. Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd., <https://domino.research.ibm.com/library/cyberdig.nsf/papers/0DABF9473B9C86D48525779800566A39/$File/Morton1966.pdf> «Còpia arxivada». Arxivat de l'original el 2019-01-25. [Consulta: 25 gener 2021].
  4. Venkat, A and Christensen, Cameron and Gyulassy, Attila and Summa, Brian and Federer, Frederick and Angelucci, Alessandra and Pascucci, Valerio «A Scalable Cyberinfrastructure for Interactive Visualization of Terascale Microscopy Data». New York Scientific Data Summit, 2016.

Bibliografia

[modifica]
  • Sagan, H. Space-Filling Curves. Springer-Verlag, 1994. 

Enllaços externs

[modifica]
  • Plane Filling Curves: the Lebesgue Curve - Cut The Knot (anglès)
  • Lebesgue 3D Curves - Visualització de la versió tridimensional de la corba