)rder
(7)
UN ALGORITHME POUR LA RECHERCHE BORNEE (RANGE SEARCH) PLUS
RAPIDE POUR DES ENSEMBLES DE POINTS À PLUSIEURS DIMENSIONS
RÉSUMÉ
Cet article décrit un algorithme pour la recherche bornée (range search) sur un ensemble de points en
2 dimensions basé sur le principe de rangée-majeure. Ces algorithmes sont très utiles pour des
applications en bathymétrie dû au grand nombre de données.
L'algorithme utilise la stratégie de "recherche bornée" qui a été dévelopée à l'Université du Nouveau-
Brunswick et basée sur la méthode de classement des points de Morton. Il n'y a aucun besoin
d'indice mais seulement une liste classée de codes de Morton. Sa performance est comparable aux
méthodes de recherche bornées les plus rapides.
La nature récursive du systéme de classement de Morton a des effets adverses sur la recherche
bornée, particuliérement sur les extensions à plusiers dimensions. Nous décrirons ces problémes et
leurs solutions. En conséquence un algorithme de recherche bornée ayant une meilleure performance
a été développé.
105