Quadtree

Quadtree adaptatiu on cada regió té un màxim d'una partícula.

En informàtica, un Quadtree (o arbre quaternari) és un tipus d'arbre d'estructura de dades utilitzat en sistemes de simulació de partícules.

La seva funció és reduir el cost computacional requerit al comprovar en tot moment i per cada partícula la posició de totes les altres partícules de la graella.[1] Per fer-ho, l'algorisme divideix la graella en quatre regions o quadrants rectangulars (tot i que existeixen variants amb altres quantitats i mides) i cadascuna de les regions és tractada com una graella sencera, de manera recursiva, fins a assolir el nombre de partícules màxim per quadrant que busquem. D'aquesta manera, per cada partícula llavors es comprova la posició de les partícules d'aquell quadrant i no de tota la graella, estalviant així la part més feixuga de la computació. El seu cost computacional és O(n log n) on n és el nombre total de partícules, mentre que sense l'algorisme el cost és d'O(n²), molt més elevat.[2]

Funció

En una simulació de partícules les forces externes poden ser aplicades per cada partícula paral·lelament, i la col·lisió de partícules només requereix la interacció de les partícules més properes, per tant tots dos casos tenen un cost computacional molt baix, de només O(n). Ara bé, altres forces aplicades a cada partícula poden dependre de tot el conjunt de partícules, per exemple la gravetat, i per tant tenen un cost computacional molt més alt, d'O(n) per cada partícula, és a dir un total d'O(n²). La funció de l'algorisme és proporcionar per cada partícula un rang de comprovació molt menor al total de la graella, de manera que es redueix el cost a O(log n) per cada partícula, és a dir un total d'O(n log n).[2]

Usos

Els Quadtree són l'anàleg en dues dimensions dels Octree, que utilitzen el mateix principi en tres dimensions, i utilitzen un sistema de partició de la graella similar als Q-tree (o arbres-Q).[3] Van ser descrits per Raphael Finkel i Jon Bentley el 1974,[1] i són utilitzats en molts de camps diferents, entre ells l'astrofísica, mecànica celeste, simulació de plasma, dinàmica molecular i dinàmica computacional de fluids.[4]

També poden ser utilitzats en la resolució d'equacions diferencials parcials el·líptiques i càlculs de la radiositat en computació gràfica.[5][6]

En general, els Quadtree s'utilitzen per realitzar simulacions de n-cossos i emmagatzemar eficientment grups de dades distribuïts a un pla.[7] La simulació de Barnes-Hut és l'algorisme més sovint utilitzat per emmagatzemar n-cossos en una estructura Quadtree o Octree.[8]

Vegeu també

  • Estructura de dades
  • Arbre binari
  • Octree
  • Arbre-B

Referències

  1. ↑ 1,0 1,1 Finkel, R. A.; Bentley, J. L. «Quad trees a data structure for retrieval on composite keys». Acta Informatica, 4, 1, 1974, pàg. 1–9. DOI: 10.1007/BF00288933 [Consulta: 6 novembre 2019].
  2. ↑ 2,0 2,1 Samet, H. «The quadtree and related hierarchical data structures». ACM Computing Surveys. ACM, 16, 2, 1984, pàg. 187–260. DOI: 10.1145/356924.356930.
  3. ↑ Aluru, S. «Quadtrees and octrees». A: Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004, p. 19-1 -- 19-26. ISBN 9781584884354. 
  4. ↑ Samet, H. «An overview of quadtrees, octrees, and related hierarchical data structures». A: Theoretical Foundations of Computer Graphics and CAD. Springer-Verlag, 1988, p. 51–68. 
  5. ↑ Har-Peled, S. «Good Triangulations and Meshing». A: Geometric approximation algorithms. Mathematical Surveys and Monographs Vol. 173, American mathematical society, 2011. 
  6. ↑ de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M. H.. «Quadtrees Non-Uniform Mesh Generation». A: Computational Geometry Algorithms and Applications. 3rd. Springer-Verlag, 2008. 
  7. ↑ Sestoft, Peter. Spreadsheet Implementation Technology: Basics and Extensions. The MIT Press, 2014, p. 60–63. ISBN 9780262526647. 
  8. ↑ Tomas G. Rokicki. «An Algorithm for Compressing Space and Time», 01-04-2006. [Consulta: 20 maig 2009].