Sortieren von Punkten, so dass der minimale euklidische Abstand zwischen aufeinanderfolgenden Punkten maximiert wird

Angesichts einer Reihe von Punkten in einem kartesischen 3D-Raum suche ich nach einem Algorithmus, der diese Punkte so sortiert, dass der minimale euklidische Abstand zwischen zwei aufeinanderfolgenden Punkten maximiert wird.

Es wäre auch vorteilhaft, wenn der Algorithmus zu einem höheren durchschnittlichen euklidischen Abstand zwischen aufeinanderfolgenden Punkten tendieren würde.

graph-algorithms cg.comp-geom optimization Lior Kogan
quelle

Crossposted , Motivation .

Jukka Suomela

Klingt nach der Maximierungsversion von Engpass-TSP . Oder die Engpassversion des Problems mit dem längsten Pfad . Hat es einen Namen?

Jukka Suomela

Ich würde empfehlen, die Gonzalez-K-Clustering-Heuristik (die gierige Strategie) zu verwenden. ohne dies vollständig durchzudenken, scheint es, als sollte es eine 2-Näherung ergeben?

Suresh Venkat

Wie bereits erwähnt, gibt Gonzalez leider keine gute Antwort (beachten Sie die Punkte (-100,0), (99,0) und (100,0)). Wenn wir zum Beispiel am falschen Punkt (-100,0) beginnen, erhalten wir eine schreckliche Antwort. Es ist immer noch möglich, dass es funktioniert, wenn Sie Gonzalez von jedem Punkt aus ausführen und die beste Antwort finden.

Suresh Venkat

Antworten:

ETA: Alles unten steht in der Veröffentlichung " Über die maximale Streuung TSP ", Arkin et al., SODA 1997.

Ich weiß keine genauen Antworten, aber hier ist ein anderer Ansatz, der sich ein wenig von Sureshs Vorschlag für Gonzalez-Clustering unterscheidet:

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

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

Dies funktioniert in jedem metrischen Raum und liefert das optimale Approximationsverhältnis zwischen Algorithmen, die in jedem metrischen Raum arbeiten. Wenn Sie sich besser als bis zu einem Faktor von zwei annähern könnten, könnten Sie Hamilton-Zyklusprobleme genau lösen, indem Sie den Eingabegraphen auf das Hamilton-Zyklusproblem in einen metrischen Raum mit Abstand 2 für jede Diagrammkante und Abstand 1 für jedes Nicht reduzieren -Kante.

Wahrscheinlich können Sie dies mit einiger Sorgfalt in einen Approximationsalgorithmus für Pfade anstelle von Zyklen einmassieren.

David Eppstein
quelle

Gibt es einen Grund zu der Annahme, dass es im euklidischen Fall kein PTAS gibt?

Jukka Suomela

Kein Grund, den ich kenne. Die üblichen PTAS-Methoden für euklidische Netzwerkentwurfsprobleme funktionieren jedoch nur zur Minimierung, nicht zur Maximierung.

David Eppstein

Eine mir bekannte Ausnahme ist das Papier von Chen und Har-Peled über ein PTAS zum Orientierungslauf im Flugzeug. Es ist ein Maximierungsproblem.

Chandra Chekuri

Wir haben einen Preprint hochgeladen, der diese Frage beantwortet, dh ein PTAS für TSP mit maximaler Streuung im euklidischen Fall. arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: Ein PTAS für euklidisches Maximum Scatter TSP)

László Kozma

Wir haben einen Preprint hochgeladen, der diese Frage beantwortet, dh ein PTAS für TSP mit maximaler Streuung im euklidischen Fall. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: Ein PTAS für euklidisches Maximum Scatter TSP)

László Kozma
quelle