La geometria de l’ordre

Anem per una carretera o camí, en un trajecte tranquil perquè volem gaudir del paisatge. Durant el trajecte, anem passant pobles. No us dic res de nou si afirmo que podem ordenar els pobles en base a quan els anem veient. Sortim del primer poble, en passem uns quants, i arribem al darrer, que és el nostre destí.

Aquest ordre, però, desapareix quan mirem els pobles al mapa, perquè ara hi ha moltíssimes maneres d’ordenar-los. Els podem ordenar per la seva latitud geogràfica, per la seva alçada sobre el nivell del mar, per la seva proximitat al mar o a una determinada ciutat, i per moltes altres variables no geogràfiques com la seva població o el nombre de bancs per seure. En les dues dimensions d’un mapa no hi ha cap ordre objectiu; en canvi, aquest ordre apareix quan caminem o anem en cotxe: les carreteres i camins ordenen els pobles. De fet, la geometria ens ho explica ben clar: tot allò que és representable al llarg d’una línia (com els pobles al llarg d’un camí o les baules en una cadena) és ordenable, mentre que allò que trobem en espais 2D, 3D o de n dimensions, és intrínsecament no ordenable. Podem ordenar-ho, és clar, però per a fer-ho ens cal afegir criteris que són extrínsecs respecte la seva posició. Aquesta multiplicitat d’ordenacions té però els seus avantatges: l’ajuntament d’un determinat poble sempre podrà trobar un criteri adient tal que, quan l’apliquin, el poble quedi el primer en l’ordenació de tots els de la seva regió o comarca. I aquí és on surten també algunes dificultats, perquè tothom acaba sent el primer en alguna cosa.

Pensem en un altre exemple. M’agradaria llogar una caseta a un poble, però no sé si tindré prou Sol a la terrassa, a l’hivern. El problema és que hi ha altres cases que no sé si em faran ombra. I la solució no és evident, perquè el problema és 3D (la posició del Sol al llarg de l’any ho és) i com acabem de veure, en aquest cas no hi ha cap ordenació intrínseca. Doncs bé, hi ha una solució elegant que ens va donar, ara fa 38 anys, l’equip d’en Henry Fuchs: podem construir un arbre de partició binària de l’espai. Perquè els arbres de partició binària de l’espai (vegeu la nota al final) estructuren la informació, sigui 2D, 3D o nD, de tal manera que contenen, de manera implícita, una infinitat de possibles ordenacions. Segons com els “llegim”, aquests arbres ens donen una ordenació o una altra. Són pots d’ordenació condensada multidimensional, estructures que ens guarden la geometria de l’ordre a l’espai. La seva bellesa, al meu entendre, és una mostra més de la poesia de l?univers.

———

Per cert, en Josep Ramoneda, parlant de les penes que demana la fiscalia Italiana als càrrecs de l’ONG Open Arms, diu que mai ningú pot ser reprimit per ajudar qui es troba en perill, i que en una societat democràtica la llei té un límit, que són els drets fonamentals de les persones. Diu també que quan aquests drets es violen, la democràcia es degrada, i que estem veient com Europa s’enfonsa al mar, per a més glòria del despotisme. Quan ho llegeixo, penso que a Europa han desaparegut l’ordre i la seva geometria.

———

NOTA: La partició binària de l’espai binari (BSP) és una manera d’estructurar un determinat espai inicial convex (per exemple, una regió cúbica) que es basa en subdividir-lo recursivament en subconjunts convexos en base a plans. Aquesta subdivisió dóna lloc a una representació dels objectes dins de l’espai basada en una estructura de dades d’arbre anomenada arbre BSP. Després d’una idea inicial de Schumacker i els seus col·laboradors l’any 1969, la proposta dels arbres BSP va ser formulada i desenvolupada en detall a partir de l’any 1980 per Henry Fuchs i els seus estudiants.

La idea és ben simple. Pensem en l’exemple de les cases i les ombres. Comencem amb una regió inicial que pot ser una capsa imaginària (convexa) que contingui, en 3D, el conjunt de totes les cases que volem estudiar. Escollim una façana d’un dels edificis més o menys centrats a la capsa inicial, i designem el seu pla P com a primer pla discriminant. Aquest pla separa i classifica totes les cases en dos grups: les que es troben a la part de davant del pla (en direcció cap enfora de la façana que ha donat lloc a aquest pla P) i aquelles que són a la seva banda del darrera. Pot donar-se el cas, és clar, que alguna casa no quedi ni al seu davant ni al darrera, sino que quedi tallada per P. En aquest cas, dividirem la casa en dues parts de manera que cada una d’elles quedi ben classificada, davant o darrera de P (de fet, una de les coses que ha de tenir en compte l’algorisme que escull el pla discriminant P, a més de subdividir el conjunt de cases en dos subconjunts acceptablement equilibrats, és el d’intentar que talli el menor nombre possible d’altres cases – en base a heurístiques que prioritzin les façanes de carrers llargs i rectes, per exemple -). Un cop hem trobat el pla discriminant P, el conjunt inicial de cases ens haurà quedat classificat en dos subconjunts: el de les que són davant de P i el de les que són al seu darrera. I cada un d’aquests dos subconjunts correspon a una regió convexa de l’espai, sub-regions R1 i R2 que provenen del fet de tallar, amb el pla P, la capsa convexa inicial. A partir d’ara, l’algorisme continua tractant, per separat, cada una d’aquestes dues sub-regions, fent-hi el mateix: cerca del pla discriminant i subdivisió del conjunt de cases entre les que són al seu davant i les que es troben al seu darrera. Per a R1, trobarà un pla P1 que la dividirà en dues sub-regions R11 i R12.  Per a R2, trobarà un pla P2 que la dividirà en dues sub-regions R21 i R22. Evidentment, P1 només actua dins de R1 i P2 només ho fa dins de R2. El procés es repeteix fins que a cada regió només hi hagi, per exemple, una casa.

L’interessant d’aquesta subdivisió recursiva de l’espai és que estructura la informació, permet la seva classificació, l’agrupa, és vàlida en 2D, en 3D i en qualsevol espai de dimensió superior nD, i a més incorpora de manera automàtica una infinitat de possibles ordenacions posteriors. Podem estructurar i organitzar a l’espai els pobles d’una comarca, les regions del cervell d’una persona o informació multidimensional d’una comarca que incorpori dades geogràfiques i de població, riquesa, salut i altres. Tot queda representat en regions polièdriques convexes que podem accedir de manera trivial tot movent-nos per un arbre de plans discriminants.

Tornem a l’exemple de les cases el Sol, les façanes i les ombres. Tindré sol a la terrassa d’aquella casa que m’agrada, el dia 10 de gener a les 4 de la tarda? L’únic que he de fer és calcular la posició (de fet, parlant amb propietat, el que he de calcular és el vector que defineix l’orientació) del Sol aquest dia a aquesta hora. Un cop sé on serà el Sol en aquest moment, comparo la seva posició amb el primer pla discriminant P. Si diem PS a la banda de P on és el Sol, i PN a l’altra banda, és evident que les cases de PS poden fer ombra a les de de PN, però que, en canvi, cap casa de PN pot fer ombra a les cases de PS. Si separo les cases en dos grups i poso primer les de PN i després les de PS, ja he fet un primer pas cap a l’ordre. L’únic que he de fer ara és repetir el procés amb els plans discriminants de PN i de PS: miro on és el Sol en relació a aquests plans i separo les cases, deixant primer les que queden separades del Sol pel pla i després les altres. Al final, aquest algorisme m’haurà generat un ordre parcial (anomenat també topològic) de manera que la primera casa en aquesta llista final ordenada pot tenir ombra de qualsevol de les altres, mentre que la darrera segur que no té ombres; per a qualsevol casa del mig de la llista, les d’abans no li poden fer ombra però les posteriors, sí. L’interessant de tot plegat és que l’ordre que obtenim depèn de la posició del Sol. L’arbre conté tots els ordres possibles de manera implícita, per a totes les possibles posicions del Sol al llarg de l’any, de manera que permet que els càlculs d’ombres siguin més eficients i ràpids.

Comenta

*

(*) Camps obligatoris

L'enviament de comentaris implica l'acceptació de les normes d'ús