Ich hab mich gestern damit beschäftigt, und denke das So ein R-Tree, oder besser noch PR-Tree. Ich denke aber dieser Algorithmus ist zu kompliziert, um ihn 1.) schnell zu verstehen und 2.) zu implementieren.

@Struppi + Alle
Danke! Das R-Tree Perl Modul ist geradezu verführerisch. Kannte ich ngar nicht! Schade nur, dass er auf 2D beschränkt ist. Die vergleichsroutinen sind hardgecoded. ICh müsste also den ganzen Code umschreiben. Es wäre schön, wenn man dort lediglich eine Sub übergibt die als Rückgabewert größer oder kleiner zurückgibt. ICh bin jetzt in Perl nicht sooo vertraut, aber in JAva würde man halt verschiedene INterfaces schreiben, so dass der Algrithmus muss allen möglichen Datenstrukturen aufgerufen werden kann.

Und ja, gern geschehen :)

@Lanx:
ICh muss dich leider enttäuschen, so ganz verstanden hab ich deinen Ansatz nicht. Aber ich möchte fast wetten, dass die Sortierung nach einzelnen Achsen noch irgendwelche Probleme beinhaltet. Aber vielleicht kannst du deinen Ansatz doch noch mal etwas mehr ausführen. Du musst natürlich kein Listing abliefern, aber vielleicht eine Art PSeudo-Code a là:
1.)Sortiere A nach [x1]
2.) ...
3.) Wenn x1 < dann gehezu 7.)
...
Natürlich nur, wenn es nicht zuviel aufwand macht.

Und ich sehe noch nicht ganz den ZUsammehang zuum Quadtree. Der Quadtree ist ein Sonderfall des R-Tree bei dem die Rechtecke klar definiert zu zerteilen sind. Beim R-Tree ist lediglich die Berechnung der optimalen Rechtecke komplizierter. Bei beiden wird aber eine Hierarchische Sortierung verwendet die ich bei deinem Ansatz nicht sehe!?

Gruß Jan