Si on cherche, étant donné n points en dimension d, à répondre à des requêtes de type "quel est le plus proche voisin de cette requête?" les méthodes classiques ont des complexités en O(polylog n) mais se révèlent en fait parfaitement inefficaces par rapport à la méthode brutale en O(n) pour des problèmes où la dimension est de quelques dizaines et le nombre de points de l'ordre de la centaine.
Un autre problème est le calcul du diamètre d'un ensemble de points. Pour des dimensions supérieures à 20, la meilleure approche connue est l'approche naïve calculant les $n^2$ distances possibles.
suggestion : une approche éventuelle consiste à utiliser le fait que les machines effectuent des opérations sur des mots de 32 bits et non de 1 bit. En dimension inférieur à 32, on essaiera de factoriser ainsi certaines opérations et de voir si on obtient des temps de calcul meilleur que la méthode brutale.
| Last modified: Tue Jan 29 08:48:36 MET 2002 | Olivier Devillers |
|
Autres stages |
|