Recherche par plage
Dans sa forme la plus générale, la recherche par plage consiste à traiter un ensemble S d'objets dans le but de déterminer lesquels sont situés à l'intérieur d'un domaine, appelé la plage de recherche. Par exemple, S peut être un ensemble de points représentant les coordonnées de villes, et l'on peut chercher quelles sont les villes situées à moins de 50 km des côtes, ou quelles sont les villes situées à moins de 100 km d'une ville donnée.
La recherche par plage est un problème fondamental en géométrie algorithmique et pour la gestion des bases de données. Les applications sont nombreuses, particulièrement pour les systèmes d'information géographiques (SIG), ou pour les programmes de dessin assisté par ordinateur (DAO). Si on considère des domaines de recherche rectangulaires, le problème s'étend facilement à des questions non-géométriques. Par exemple, "quels sont les individus entre 20 et 30 ans habitant Paris et gagnant plus de 1500 euros par mois ?".
Variantes
On distingue plusieurs variantes du problèmes, en fonction des questions posées :
- le type d'objet manipulé. Il s'agit le plus souvent de points, mais on peut aussi considérer des segments, des polygones, des rectangles...
- le type de domaine de recherche. Le plus simple est de considérer un rectangle avec les côtés parallèles aux axes principaux. Les extensions considèrent un rectangle quelconque, un simplexe, un polygone, une sphère...
- le type de question. On peut chercher si à déterminer les objets à l'intérieur du domaine de recherche, savoir si cet ensemble est vide ou non, chercher leur nombre...
Voir aussi
- Arbre kd, qui est une des structures de données de référence pour la recherche par plage.
- Arbre de portée
Références
- Robert Sedgewick, Algorithmes en langage C, Dunod: 2001, ch. 26 p. 393. (ISBN 2-10-005331-0)
- de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry, 2nd Edition. Berlin: Springer, 2000. ch. 5 and 16. (ISBN 3-540-65620-0)
- Jiřà Matoušek. Geometric range searching. ACM Computing Surveys, 26(4):421-461, 1994.
- Pankaj K. Agarwal, and Jeff Erickson. Geometric range searching and its relatives. In Bernard Chazelle, Jacob Goodman, and Richard Pollack, editors, Advances in Discrete and Computational Geometry, pages 1–56. American Mathematical Society, 1998.