Struppi+2009-01-29 00:49:50--

Mir war Euklid bis heute unbekannt und versuche Tree::R gerade zu analysieren.

Euklidischer Abstand ist nichts anderes als der triviale Abstand im (euklidischen) Anschauungsraum (also so wie man's "kennt") und das mit nem verallgemeinerten Pythagoras ausgerechnet.
Im R² trivialerweise der normale Pythagoras also Abstand²=delta_x²+delta_y².

Mathematiker kennen halt diverse Räume und Abstandsbegriffe, deswegen ziehen sie den Schöpfer der antiken Geometrie zur Bezeichnung des "trivialen Falles" heran.

R-Trees teilen den Raum schrittweise in immer kleinere Teilräume auf, z.B. den R² in 4 Quadranten um den Mittelpukt im ersten Schritt dann diese wiederum in Quadranten usw. Im R³ wärens dann entsprechend 8 Quader usw. Die Idee ist dabei im Suchbaum nur noch wenige Quadranten weiter unterteilen zu müssen, weil der Suchradius schnell schrumpft und entfernte Quadranten fix ausschließt.

Ich denke R-Trees sind wahrscheinlich cleverer als einfach nur mittig zu teilen, aber ich hoffe die Idee wird klar.
EDIT: Schau an der von mir beschriebene Sonderfall ist als Quadtree bei WP bekannt!