Accueil🇫🇷Chercher

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.

Recherche opérationnelle par l'algorithme du simplexe

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

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.
    Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.