Clasificación de puntos de modo que se maximice la distancia euclidiana mínima entre puntos consecutivos

Dado un conjunto de puntos en un espacio cartesiano 3D, estoy buscando un algoritmo que clasifique estos puntos, de modo que se maximice la distancia euclidiana mínima entre dos puntos consecutivos.

También sería beneficioso si el algoritmo tuviera una tendencia hacia una distancia euclidiana promedio más alta entre puntos consecutivos.

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

Crossposted , motivación .

Jukka Suomela

Suena como la versión de maximización del cuello de botella TSP . O la versión del cuello de botella del problema del camino más largo . Eso tiene un nombre?

Jukka Suomela

Recomiendo usar la heurística gonzalez k-clustering (la estrategia codiciosa). sin pensarlo completamente, ¿parece que debería producir una aproximación de 2?

Suresh Venkat

Desafortunadamente, como se dijo, González no dará una buena respuesta (considere los puntos (-100,0), (99,0) y (100,0)). Si comenzamos en el punto equivocado (-100,0), por ejemplo, obtenemos una respuesta terrible. Todavía es posible que ejecutar gonzalez desde todos los puntos y tomar la mejor respuesta funcione.

Suresh Venkat

Respuestas:

ETA: Todo lo que se encuentra debajo está en el documento " Sobre la dispersión máxima TSP ", Arkin et al, SODA 1997.

No sé sobre respuestas exactas, pero aquí hay otro enfoque que es un poco diferente de la sugerencia de Suresh de la agrupación de González:

Supongamos por simplicidad que es par. Para cada vértice , encuentre la mediana de las distancias . Forme un gráfico no dirigido en el que cada vértice esté conectado a los otros vértices que están al menos a la distancia media de distancia. El grado mínimo en este gráfico es al menos , por lo que según el teorema de Dirac es posible encontrar un ciclo hamiltoniano en este gráfico. $n$ $p$ $n-1$ $d(p,q)$ $p$ $n/2$

Por otro lado, hay vértices en el disco centrados en con radio , demasiados para formar un conjunto independiente en el ciclo, por lo que cualquier ciclo hamiltoniano debería tener una conexión de borde unos dos de estos vértices, de longitud como máximo . Por lo tanto, el ciclo hamiltoniano encontrado por este algoritmo es, en el peor de los casos, una aproximación de 2 al ciclo máximo del cuello de botella. $n/2 + 1$ $p$ $d(p,q)$ $2d(p,q)$

Esto funcionará en cualquier espacio métrico y proporciona la relación de aproximación óptima entre algoritmos que funcionan en cualquier espacio métrico. Porque, si pudiera aproximarse mejor que dentro de un factor de dos, entonces podría resolver exactamente los problemas del ciclo hamiltoniano, reduciendo el gráfico de entrada al problema del ciclo hamiltoniano en un espacio métrico con distancia 2 para cada borde del gráfico y distancia 1 para cada no -borde.

Probablemente con un poco de cuidado puede dar masajes a esto en un algoritmo de aproximación para rutas en lugar de ciclos.

David Eppstein
fuente

¿Hay alguna razón para creer que no hay PTAS en el caso euclidiano?

Jukka Suomela

No hay razón que yo sepa. Pero los métodos habituales de PTAS para problemas de diseño de red euclidiana solo funcionan para minimizar, no para maximizar.

David Eppstein el

Una excepción que conozco es el papel de Chen y Har-Peled en un PTAS para Orientación en el avión. Es un problema de maximización.

Chandra Chekuri

Cargamos un preprint que aborda esta pregunta, es decir, proporciona un PTAS para TSP de dispersión máxima en el caso euclidiano. arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)

László Kozma

Cargamos un preprint que aborda esta pregunta, es decir, proporciona un PTAS para TSP de dispersión máxima en el caso euclidiano. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)

László Kozma
fuente