Recherche par plage

Cet article est une ébauche concernant la géométrie et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Recherche opérationnelle par l'algorithme du simplexe[Quoi ?]

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

Références