Sélection des points les plus dispersés dans un ensemble de points

Existe-t-il un algorithme (efficace) pour sélectionner un sous-ensemble de points dans un ensemble de points ( ) de telle sorte qu'ils "couvrent" la plus grande partie de la zone (sur tous les sous-ensembles possibles de taille )?$M$$N$$M < N$$M$

Je suppose que les points sont dans un plan 2D.

L'algorithme naïf est simple, mais prohibitif en termes de complexité temporelle:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Je recherche une méthode plus efficace voire approximative.

Exemple, voici un avion avec quelques points aléatoires:

Pour , je m'attends à sélectionner des points comme ceux-ci:$M=5$

Notez que les points sélectionnés (rouges) sont dispersés sur tout le plan.

J'ai trouvé un article " SÉLECTIONNER EFFICACEMENT LES POINTS CLÉS SPATIALEMENT DISTRIBUÉS POUR LE SUIVI VISUEL " qui est lié à ce problème. Cependant, cela suppose que les points sont pondérés.

Voici une solution approximative. Puisque N est si grand et M est si petit, que diriez-vous de ce qui suit:

1. Calculer la coque convexe de N
2. Sélectionnez jusqu'à M points de la coque qui répondent à vos critères de distance maximale.
3. Si l'étape 2 vous laisse moins de M points, sélectionnez 1 point de l'intérieur qui maximise sa distance par rapport aux points précédemment sélectionnés.
4. Répétez l'étape 3 jusqu'à ce que le nombre de points sélectionnés soit M

L'intuition derrière cela est que depuis N >> M , et que vous voulez des points aussi éloignés les uns des autres que possible, ils seront probablement proches des bords des données, vous pouvez donc aussi bien commencer par la coque, puis de manière itérative travaillez votre chemin à partir de là.

De plus, en commençant par la coque, vous réduisez votre recherche initiale de N à N ^1/2 .

MISE À JOUR

Si les étapes 3 et 4 ci-dessus prennent trop de temps (puisque vous testez de manière itérative l'intérieur de votre ensemble de données), deux autres idées me sont venues à l'esprit pour accélérer votre problème.

1. Recherche aléatoire : Supposons que vous ayez trouvé des points P sur la coque à l'étape 2. Ensuite, tirez au hasard M - P points de l'intérieur. Sélectionnez le meilleur ensemble après X essais.
2. Recuit simulé : calculez le plus petit cadre englobant qui couvre votre jeu de données (n'a pas besoin d'être aligné avec les axes, peut être incliné). Définissez ensuite un ensemble de M points de grille uniformément répartis sur cette boîte englobante. Notez que ces points ne coïncident pas nécessairement avec l'un de vos points de jeu de données. Ensuite, pour chaque point de grille, recherchez les k voisins les plus proches dans votre jeu de données. Parcourez chaque combinaison M x k et sélectionnez celle qui répond à vos critères de distance maximale. En d'autres termes, vous utilisez la grille initiale comme bootstrap pour trouver une bonne solution initiale.

$N$$M$

$M$$M$

$M$$1$$M=3,4,5$

$M=3$$1$$M=4$$M=5$$1$

Si nous voulons éviter une sélection prédominante de points à la périphérie, un objectif différent peut s'avérer utile. La maximisation de la distance minimale entre les points est un tel critère. Des problèmes connexes ont été abordés chez StackOverflow , Computer Science SE , Math.SE et MathOverflow .

$M$$D$$M$$D$

OK, vous voulez donc sélectionner M points dans un ensemble donné de N points dans le plan euclidien, afin que la somme des distances par paire des points sélectionnés soit maximale, n'est-ce pas?

L'algorithme de recherche locale standard est assez rapide et offre une assez bonne approximation. Le temps d'exécution est linéaire en N et quadratique en M. Son rapport d'approximation est de 1 à 4 / M. Cela signifie que le rapport s'améliore à mesure que M augmente. Par exemple, pour M = 10, elle obtient 60% de la valeur optimale et pour M = 50, elle obtient 92% de la valeur optimale.

L'algorithme fonctionne également pour les espaces euclidiens de dimension générale. Dans ce cas, le problème est NP-difficile. Mais dans l'avion, on ne sait pas s'il est dur NP.

La source est cet article . J'espère que cela t'aides! Bien, Alfonso

Une solution est:

• $O(n)$

• Faites M artificiels, même des points répartis à l'intérieur de ce rectangle englobant, certains M sont plus difficiles que d'autres. Dans votre cas, quatre dans les coins du rectangle et un au centre

• $O(n(log(n)))$

• $O(m(log(n)))$

$O(n(log(n)))$$\sqrt{M} \in \mathbb{N}$