J'ai fait un programme pour implémenter l'algorithme Gift Wrapping de trouver la coque convexe. Y at-il un moyen de générer un ensemble de points qui sert de pire cas pour cet algorithme?Quel est le pire des cas pour l'algorithme de don-wapping (Algorithme de Jarvis) pour calculer la coque convexe?
Comment vais-je générer un tel cas?
Supposons que vous ayez un ensemble de points - S. Quand à chaque itération vous soustrayez un point de S et ajouter ce point à une coque convexe et vous devez vérifier tous les points ce qui laisse encore à S.
Le Le temps d'exécution dépend de la taille de la sortie, donc la marche de Jarvis est un algorithme sensible à la sortie.
Donc, plus grande sortie - plus de temps nécessaire. Et cela peut être réalisé sur l'ensemble qui est la coque convexe de lui-même.
Probablement le moyen le plus simple de générer une telle coque convexe de n le met tous les points sur un cercle.
Si je suis droite, le pire des cas est lorsque H = N, à savoir l'ensemble de test est formée par les sommets d'un polygone convexe. –