Problèmes de proximité

Les problèmes de proximité sont une classe de problèmes de géométrie computationnelle qui impliquent l'estimation des distances entre des objets géométriques.

Un sous-ensemble de ces problèmes énoncés en termes de points uniquement est parfois appelé problèmes du point le plus proche , bien que le terme « problème du point le plus proche » soit également utilisé comme synonyme de recherche du voisin le plus proche .

Un trait commun à beaucoup de ces problèmes est la possibilité d'établir la limite inférieure Θ ( n log n ) de leur complexité de calcul par réduction à partir du problème d'unicité des éléments en se basant sur l'observation selon laquelle s'il existe un algorithme efficace pour calculer une sorte de distance minimale pour un ensemble d'objets, il est trivial de vérifier si cette distance est égale à 0.

Bien que ces problèmes ne posent aucun problème de complexité informatique, certains d’entre eux sont remarquables en raison de leur omniprésence dans les applications informatiques de la géométrie.

• Distance entre deux segments de droite . Elle ne peut pas être exprimée par une formule unique, contrairement, par exemple, à la distance d'un point à une droite . Son calcul nécessite une énumération minutieuse des configurations possibles, notamment en 3D et dans les dimensions supérieures.
• Boîte englobante , l' hyperrectangle minimal aligné sur l'axe qui contient toutes les données géométriques

• Paire de points la plus proche : Étant donné N points, trouvez-en deux avec la plus petite distance entre eux
• Requête du point le plus proche / requête du voisin le plus proche : Étant donné N points, trouvez celui qui a la plus petite distance par rapport à un point de requête donné.
• Problème de tous les voisins les plus proches (construction du graphe des voisins les plus proches ) : Étant donné N points, trouver le plus proche pour chacun d'eux
• Diamètre d'un ensemble de points : Étant donné N points, trouvez-en deux avec la plus grande distance entre eux
• Largeur d'un ensemble de points : Étant donné N points, trouver deux (hyper)plans avec la plus petite distance entre eux et avec tous les points entre eux
• Arbre couvrant minimal pour un ensemble de points
  • Arbre couvrant minimal euclidien
• Triangulation de Delaunay
• Diagramme de Voronoi
• Plus petite sphère englobante : Étant donné N points, trouver la plus petite sphère (cercle) les englobant tous
• Plus grand cercle vide : Étant donné N points dans le plan, trouver un plus grand cercle centré dans leur enveloppe convexe et n'enfermant aucun
• Plus petit rectangle englobant : contrairement au problème de la boîte englobante mentionné ci-dessus, le rectangle peut être de n'importe quelle orientation
• Le plus grand rectangle vide
• Clé géométrique , un graphe pondéré sur un ensemble de points comme sommets qui, pour chaque paire de sommets, a un chemin entre eux d'un poids au plus égal à « k » fois la distance spatiale entre ces points pour un « k » fixe.

• Le chemin le plus court parmi les obstacles
• Distance d'approche la plus proche

• Franco P. Preparata et Michael Ian Shamos (1985). Géométrie computationnelle - Une introduction . Springer-Verlag . ISBN 0-387-96131-3. 1ère édition : ISBN 0-387-96131-3 ; 2ème impression, corrigée et augmentée, 1988 : ISBN 3-540-96131-3 ; Traduction russe, 1989 : ISBN 5-03-001041-6 . Les problèmes de proximité sont traités dans les chapitres 6 et 7.