Tri des points de manière à maximiser la distance euclidienne minimale entre les points consécutifs

Étant donné un ensemble de points dans un espace cartésien 3D, je recherche un algorithme qui triera ces points, de sorte que la distance euclidienne minimale entre deux points consécutifs soit maximisée.

Il serait également avantageux que l'algorithme tende vers une distance euclidienne moyenne plus élevée entre des points consécutifs.

graph-algorithms cg.comp-geom optimization Lior Kogan
la source

Crossposted , motivation .

Jukka Suomela

Cela ressemble à la version de maximisation du goulot d' étranglement TSP . Ou la version goulot d'étranglement du problème de chemin le plus long . At-il un nom?

Jukka Suomela

Je recommanderais d'utiliser l'heuristique gonzalez k-clustering (la stratégie gourmande). sans y penser complètement, il semble que cela devrait donner une approximation à 2?

Suresh Venkat

Malheureusement, comme indiqué, Gonzalez ne donnera pas une bonne réponse (considérez les points (-100,0), (99,0) et (100,0)). Si nous partons du mauvais point (-100,0) par exemple, nous obtenons une réponse terrible. Il est toujours possible que l'exécution de gonzalez à partir de tous les points et la meilleure réponse fonctionnent.

Suresh Venkat

Réponses:

ETA: Tout ce qui suit est dans l'article " Sur le TSP à diffusion maximale ", Arkin et al, SODA 1997.

Je ne connais pas les réponses exactes, mais voici une autre approche qui est un peu différente de la suggestion de Suresh de regrouper Gonzalez:

$n$ $p$ $n-1$ $d(p,q)$ $p$ $n/2$

$n/2 + 1$ $p$ $d(p,q)$ $2d(p,q)$

Cela fonctionnera dans n'importe quel espace métrique et donnera le rapport d'approximation optimal parmi les algorithmes qui fonctionnent dans n'importe quel espace métrique. Car, si vous pouviez vous rapprocher mieux que dans un facteur de deux, alors vous pourriez résoudre les problèmes de cycle hamiltonien exactement, en réduisant le graphique d'entrée au problème de cycle hamiltonien dans un espace métrique avec la distance 2 pour chaque bord de graphique et la distance 1 pour chaque non -bord.

Probablement avec un peu de soin, vous pouvez masser cela en un algorithme d'approximation pour les chemins plutôt que pour les cycles.

David Eppstein
la source

Y a-t-il une raison de croire qu'il n'y a pas de PTAS dans le cas euclidien?

Jukka Suomela

Aucune raison que je sache. Mais les méthodes PTAS habituelles pour les problèmes de conception de réseaux euclidiens ne fonctionnent que pour la minimisation, pas la maximisation.

David Eppstein

Une exception que je connaisse est le papier de Chen et Har-Peled sur un PTAS pour la course d'orientation dans l'avion. C'est un problème de maximisation.

Chandra Chekuri

Nous avons téléchargé une préimpression qui répond à cette question, c'est-à-dire qui donne un PTAS pour le TSP à dispersion maximale dans le cas euclidien. arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)

László Kozma

Nous avons téléchargé une préimpression qui répond à cette question, c'est-à-dire qui donne un PTAS pour le TSP à dispersion maximale dans le cas euclidien. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)

László Kozma
la source