J'ai deux ensembles de points, A et B. Je suis à la recherche du sous-ensemble de A dont la coque convexe contient au plus n points en B etla plus grande coque convexe A ne contenant pas de points dans B
L'une ou l'autre serait OK.
Existe-t-il un algorithme efficace? Mon problème est 2D.
Je ne sais pas comment craquer celui-ci. Mais je commencerais par une triangulation de Delaunay de A et comptais les points à l'intérieur de chaque triangle. Maintenant, nous voulons maximiser la surface (2D à droite, le volume était un glissement?) Ou le nombre de points, sur un sous-ensemble convexe.
Maintenant, chaque triangle est convexe. Nous marquons tous avec plus de n points comme «mauvais», mais nous assignons des points, ces triangles ne peuvent pas être inclus. Le reste sont des candidats. Pour chaque candidat, allez voir ses voisins et essayez de le faire pousser. Donc, nous obtenons environ 3 * le nombre de triangles en tant que candidats quadruples composites, et chaque triangles développés avec succès n'est plus un candidat, mais toujours pas "mauvais". Tous les quads doivent être convexes. Si un triangle ne grandit pas du tout, il reste un "candidat", mais il est "fini". Dès qu'un meilleur candidat émerge, il n'est plus un candidat et devient "mauvais", aucun ensemble réussi peut inclure il.
Maintenant, pour la prochaine étape, c'est la même idée de base, essayez de vous unir avec tous les voisins possibles et éliminer de la liste des candidats tout ce que vous absorber. Si vous ne pouvez pas grandir avec succès, vous devenez "fini". Mais vous ne pouvez pas vous unir avec n'importe qui, sinon convexe, vous devez ajouter triangles supplémentaires pour devenir convexe.
Éventuellement, tous nos candidats seront soit absorbés ou «finis», et nous avons un gagnant. La question est de savoir si cet algorithme va créer une explosion exponentielle de candidats ou si nous pouvons les éliminer assez rapidement pour éviter que cela se produise. Je ne connais pas la réponse à cela. Mais je pense que si vous essayez de vous unir avec les plus grands voisins en premier, vous pouvez très rapidement éliminer la plupart des sous-ensembles possibles.