Den Quad-Tree gibt es übrigens auch schon in Perl:
QuadTree

Ist allerdings auch für 2-Dimensionale Problem. Aber ich glaube, dass man diesen Algorithmus noch am einfachsten umsetzen kann.

Weitere IDeen sind erwünscht :)

Jan