Algorithme de Fortune pour Diagramme de Voronoï

Fermé
Deepkdd Messages postés 8 Date d'inscription dimanche 12 avril 2015 Statut Membre Dernière intervention 17 juin 2016 - 17 juin 2016 à 04:01
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 17 juin 2016 à 20:42
Bonjour à tous,

Soit P un ensemble de n points dans le plan. Donner une O (n log n) algorithme de temps pour trouver pour chaque point p dans P un autre point P qui est le plus proche. (Indice: Votre algorithme peut être basé sur l'algorithme de la Fortune pour calculer le diagramme de Voronoï des points dans P.)

Je cherche juste une idée de méthode pour faire un algorithme super optimisé.

Merci de m'avoir lu
A voir également:

1 réponse

KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
17 juin 2016 à 07:55
Bonjour,

"Je cherche juste une idée de méthode pour faire un algorithme super optimisé."
C'est marqué dans le titre : utilise l'algorithme de Fortune...
0
Deepkdd Messages postés 8 Date d'inscription dimanche 12 avril 2015 Statut Membre Dernière intervention 17 juin 2016
17 juin 2016 à 15:07
mais comment je peux utilise l'algorithme de fortune sur cet prblm
0
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
17 juin 2016 à 20:42
L'algorithme de Fortune te permet d'obtenir le diagramme de Voronoi dont tu déduis la triangulation de Delaunay qui te donnent les points les plus proches...
Alternative : tu peux utiliser un autre algorithme pour obtenir directement la triangulation de Delaunay, mais j'imagine que si on te parle du diagramme de Voronoi c'est parce que que tu as déjà du faire l'algo dans un autre exercice.
0