Le but premier de la recherche en géométrie computationnelle combinatoire est de développer des algorithmes et des structures de données efficaces pour résoudre des problèmes énoncés en termes d’objets géométriques de base : points, segments de ligne, polygones, polyèdres, etc.
Certains de ces problèmes semblent si simples qu’ils n’étaient pas du tout considérés comme des problèmes avant l’avènement des ordinateurs. Considérons, par exemple, le problème de la paire la plus proche :
- Donné n points dans le plan, trouver les deux avec la plus petite distance l’un de l’autre.
On pourrait calculer les distances entre toutes les paires de points, dont il y a n(n-1)/2, puis choisir la paire avec la plus petite distance. Cet algorithme de force brute prend O(n2) temps, c’est-à-dire que son temps d’exécution est proportionnel au carré du nombre de points. Un résultat classique en géométrie computationnelle a été la formulation d’un algorithme qui prend O(n log n). Des algorithmes aléatoires qui prennent O(n) temps prévu, ainsi qu’un algorithme déterministe qui prend O(n log log n) temps, ont également été découverts.
Classes de problèmesEdit
Les problèmes centraux de la géométrie computationnelle peuvent être classés de différentes manières, selon divers critères. On peut distinguer les classes générales suivantes.
Problèmes statiquesEdit
Dans les problèmes de cette catégorie, une certaine entrée est donnée et la sortie correspondante doit être construite ou trouvée. Certains problèmes fondamentaux de ce type sont :
- Coque convexe : Étant donné un ensemble de points, trouver le plus petit polyèdre/polygone convexe contenant tous les points.
- Intersection de segments de lignes : Trouver les intersections entre un ensemble donné de segments de ligne.
- Triangulation de Delaunay
- Diagramme de Voronoï : Étant donné un ensemble de points, partitionner l’espace en fonction des points les plus proches des points donnés.
- Programmation linéaire
- Paire de points la plus proche : Étant donné un ensemble de points, trouvez les deux avec la plus petite distance entre eux.
- Paire de points la plus éloignée
- Le plus grand cercle vide : Étant donné un ensemble de points, trouver un plus grand cercle dont le centre est à l’intérieur de leur coque convexe et n’en enfermant aucun.
- Plus court chemin euclidien : Relier deux points dans un espace euclidien (avec obstacles polyédriques) par un plus court chemin.
- Triangulation d’un polygone : Étant donné un polygone, partitionner son intérieur en triangles
- Génération de maillage
- Opérations booléennes sur les polygones
La complexité de calcul pour cette classe de problèmes est estimée par le temps et l’espace (mémoire de l’ordinateur) nécessaires pour résoudre une instance de problème donnée.
Problèmes d’interrogation géométriqueEdit
Dans les problèmes d’interrogation géométrique, communément appelés problèmes de recherche géométrique, l’entrée est constituée de deux parties : la partie espace de recherche et la partie interrogation, qui varie sur les instances du problème. L’espace de recherche doit généralement être prétraité, de manière à pouvoir répondre efficacement à plusieurs requêtes.
Certains problèmes fondamentaux de recherche géométrique sont :
- Recherche de plage : prétraiter un ensemble de points, afin de compter efficacement le nombre de points à l’intérieur d’une région de requête.
- Localisation de points : Étant donné une partition de l’espace en cellules, produire une structure de données qui indique efficacement dans quelle cellule se trouve un point de requête.
- Plus proche voisin : Prétraiter un ensemble de points, afin de trouver efficacement quel point est le plus proche d’un point de requête.
- Ray tracing : Étant donné un ensemble d’objets dans l’espace, produire une structure de données qui indique efficacement quel objet un rayon de requête intersecte en premier.
Si l’espace de recherche est fixe, la complexité de calcul pour cette classe de problèmes est généralement estimée par :
- le temps et l’espace nécessaires pour construire la structure de données à rechercher
- le temps (et parfois un espace supplémentaire) pour répondre aux requêtes.
Pour le cas où l’espace de recherche est autorisé à varier, voir « Problèmes dynamiques ».
Problèmes dynamiquesModification
Enfin, une autre grande classe est celle des problèmes dynamiques, dans lesquels le but est de trouver un algorithme efficace pour trouver une solution de manière répétée après chaque modification incrémentale des données d’entrée (ajout ou suppression d’éléments géométriques d’entrée). Les algorithmes pour les problèmes de ce type impliquent généralement des structures de données dynamiques. N’importe quel problème de calcul géométrique peut être converti en un problème dynamique, au prix d’un temps de traitement accru. Par exemple, le problème de recherche de plage peut être converti en un problème de recherche de plage dynamique en prévoyant l’ajout et/ou la suppression de points. Le problème de la coque convexe dynamique consiste à garder la trace de la coque convexe, par exemple, pour l’ensemble de points qui change dynamiquement, c’est-à-dire, alors que les points d’entrée sont insérés ou supprimés.
La complexité de calcul pour cette classe de problèmes est estimée par :
- le temps et l’espace nécessaires pour construire la structure de données à rechercher
- le temps et l’espace pour modifier la structure de données recherchée après un changement incrémental dans l’espace de recherche
- le temps (et parfois un espace supplémentaire) pour répondre à une requête.
VariationsEdit
Certains problèmes peuvent être traités comme appartenant à l’une ou l’autre des catégories, selon le contexte. Par exemple, considérez le problème suivant.
- Point dans un polygone : Décider si un point est à l’intérieur ou à l’extérieur d’un polygone donné.
Dans de nombreuses applications, ce problème est traité comme un problème à un seul coup, c’est-à-dire qu’il appartient à la première catégorie. Par exemple, dans de nombreuses applications d’infographie, un problème courant est de trouver quelle zone de l’écran est cliquée par un pointeur. Cependant, dans certaines applications, le polygone en question est invariant, tandis que le point représente une requête. Par exemple, le polygone d’entrée peut représenter la frontière d’un pays et le point est la position d’un avion, et le problème est de déterminer si l’avion a violé la frontière. Enfin, dans l’exemple précédemment mentionné de l’infographie, dans les applications de CAO, les données d’entrée changeantes sont souvent stockées dans des structures de données dynamiques, qui peuvent être exploitées pour accélérer les requêtes point dans polygone.
Dans certains contextes de problèmes de requêtes, il existe des attentes raisonnables sur la séquence des requêtes, qui peuvent être exploitées soit pour des structures de données efficaces, soit pour des estimations plus serrées de la complexité de calcul. Par exemple, dans certains cas, il est important de connaître le pire cas pour le temps total de la séquence entière de N requêtes, plutôt que pour une seule requête. Voir aussi « analyse amortie ».