Recherche par plage

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

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.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recherche par plage de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Recherche genealogique en France — Recherche généalogique en France Sommaire 1 Les sources et les méthodes de recherche 1.1 Découpages administratifs 1.2 Délai de communication 1.3 Les mairies …   Wikipédia en Français

  • Recherche généalogique en france — Sommaire 1 Les sources et les méthodes de recherche 1.1 Découpages administratifs 1.2 Délai de communication 1.3 Les mairies …   Wikipédia en Français

  • Plage naturiste — Naturisme Pour les articles homonymes, voir Naturisme (homonymie). Selon la définition adoptée par le XIVe Congrès international de la Fédération naturiste internationale (INF FNI, Agde, 1974), le naturisme est : « une manière de vivre… …   Wikipédia en Français

  • plage — 1. plage [ plaʒ ] n. f. • 1290; var. plaie; lat. plaga ♦ Littér. et vx Étendue de terre. « des plages sablonneuses, labourées par les pluies de l hiver, brûlées par les feux de l été » (Chateaubriand). Par ext. Plage de mer : étendue de mer.… …   Encyclopédie Universelle

  • Plage braille — Une plage braille et un clavier. Une plage braille (en anglais refreshable Braille display) est un dispositif électro mécanique utilisé par les aveugles pour afficher en temps réel des caractères braille, le plus souvent issus d un ordinateur.… …   Wikipédia en Français

  • Recherche généalogique en France — Sommaire 1 Les sources et les méthodes de recherche 1.1 Découpages administratifs 1.2 Délai de communication 1.3 Les mairies …   Wikipédia en Français

  • Télédétection par radar — Radar Pour les articles homonymes, voir Radar (homonymie). Cette antenne radar longue portée, connue sous le nom ALTAIR, est utilisée pour détecter et pister les objets spatiaux …   Wikipédia en Français

  • Compression par ondelettes — La Compression par ondelettes est une technique de compression de données, bien adaptée à la compression d images. Sommaire 1 Introduction aux ondelettes 2 Algorithme ondelettes 3 Transformée ondelettes …   Wikipédia en Français

  • Histoire Des Rues Du Touquet-Paris-Plage — Cet article décrit l histoire des rues du Touquet Paris Plage. Classement des rues dans l ordre officiel des documents municipaux Sommaire : Haut A B C D E F G H …   Wikipédia en Français

  • Histoire des rues du Touquet-Paris-Plage — Article principal : Le Touquet Paris Plage. Cet article décrit l histoire des rues du Touquet Paris Plage. Le classement des rues reprend celui qui est utilisé dans les documents municipaux. Sommaire : Ha …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”