Worldlex Wiki 
En géométrie algorithmique , un algorithme de balayage linéaire ou planaire est un paradigme algorithmique qui utilise une ligne ou une surface de balayage conceptuelle pour résoudre divers problèmes dans l'espace euclidien . C'est une technique fondamentale en géométrie algorithmique.
Le principe de ces algorithmes est d'imaginer qu'une ligne (souvent verticale) balaie le plan, s'arrêtant à certains points. Les opérations géométriques se limitent aux objets qui intersectent ou se trouvent à proximité immédiate de la ligne de balayage lorsqu'elle s'arrête, et la solution complète est obtenue une fois que la ligne a survolé tous les objets.
Applications
L'application de cette approche a permis une avancée majeure dans la complexité de calcul des algorithmes géométriques lorsque Shamos et Hoey ont présenté, en 1976, des algorithmes pour l'intersection de segments de droite dans le plan. Ils ont notamment décrit comment la combinaison de l'approche par balayage linéaire avec des structures de données efficaces ( arbres binaires de recherche auto-équilibrés ) permet de détecter les intersections entre complexité temporelle de O ( N log N ) . L' algorithme de Bentley-Ottmann, étroitement apparenté , utilise une technique de balayage linéaire pour identifier les diagramme de Voronoi ( algorithme de Fortune ) et la triangulation de Delaunay ou les opérations booléennes sur les polygones .
Généralisations et extensions
Le balayage topologique est une forme de balayage plan avec un ordre simple des points de traitement, ce qui évite la nécessité de trier complètement les points ; il permet d'exécuter plus efficacement certains algorithmes de balayage de ligne.
La technique du compas rotatif pour la conception d'algorithmes géométriques peut également être interprétée comme une forme de balayage planaire, dans le dual projectif du plan d'entrée : une forme de dualité projective transforme la pente d'une droite dans un plan en la coordonnée x d'un point dans le plan dual, de sorte que la progression à travers les droites triées par ordre de pente, telle qu'effectuée par un algorithme de compas rotatif, est duale à la progression à travers les points triés par leurs coordonnées x dans un algorithme de balayage planaire.
L'approche par balayage peut être généralisée à des dimensions supérieures.