Classificação de pontos para que a distância euclidiana mínima entre pontos consecutivos seja maximizada

Dado um conjunto de pontos em um espaço cartesiano 3D, estou procurando um algoritmo que classifique esses pontos, de modo que a distância euclidiana mínima entre dois pontos consecutivos seja maximizada.

Também seria benéfico se o algoritmo tivesse uma tendência a uma distância euclidiana média mais alta entre pontos consecutivos.

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

Crossposted , motivação .

Jukka Suomela 13/10/11

Parece a versão de maximização do TSP de gargalo . Ou a versão do gargalo do problema de caminho mais longo . Isso tem um nome?

Jukka Suomela 13/10/11

Eu recomendaria usar a heurística gonzalez k-clustering (a estratégia gananciosa). sem pensar nisso completamente, parece que deveria render uma aproximação de 2?

Suresh Venkat

Infelizmente, como afirmado, Gonzalez não dará uma boa resposta (considere os pontos (-100,0), (99,0) e (100,0)). Se começarmos no ponto errado (-100,0), por exemplo, obteremos uma resposta terrível. Ainda é possível que executar gonzalez de todos os pontos e obter a melhor resposta funcione.

Suresh Venkat

Respostas:

ETA: Tudo abaixo está no artigo " No TSP de dispersão máxima ", Arkin et al, SODA 1997.

Não sei as respostas exatas, mas aqui está outra abordagem um pouco diferente da sugestão de Suresh sobre o agrupamento de Gonzalez:

Assuma, por simplicidade, que é par. Para cada vértice , encontre a mediana das distâncias . Forme um gráfico não direcionado no qual cada vértice esteja conectado aos outros vértices que estão pelo menos a distância média. O grau mínimo neste gráfico é pelo menos , portanto, pelo teorema de Dirac, é possível encontrar um ciclo hamiltoniano neste gráfico. $n$ $p$ $n-1$ $d(p,q)$ $p$ $n/2$

Por outro lado, existem vértices no disco centrado em com raio , muitos para formar um conjunto independente no ciclo, portanto, qualquer ciclo hamiltoniano teria que ter uma borda conectando alguns desses vértices, com comprimento no máximo . Portanto, o ciclo hamiltoniano encontrado por esse algoritmo é na pior das hipóteses uma aproximação de 2 ao ciclo máximo de gargalo. $n/2 + 1$ $p$ $d(p,q)$ $2d(p,q)$

Isso funcionará em qualquer espaço métrico e fornece a taxa de aproximação ideal entre algoritmos que funcionam em qualquer espaço métrico. Pois, se você puder aproximar-se melhor do que dentro de um fator de dois, poderá resolver exatamente os problemas do ciclo hamiltoniano, reduzindo o gráfico de entrada ao problema do ciclo hamiltoniano em um espaço métrico com distância 2 para cada extremidade do gráfico e distância 1 para cada não -Beira.

Provavelmente, com algum cuidado, você pode massagear isso em um algoritmo de aproximação para caminhos, em vez de ciclos.

David Eppstein
fonte

Existe alguma razão para acreditar que não há PTAS no caso euclidiano?

Jukka Suomela 13/10/11

Nenhuma razão que eu saiba. Mas os métodos usuais de PTAS para problemas de projeto de rede euclidiana funcionam apenas para minimização, não maximização.

David Eppstein

Uma exceção que conheço é o artigo de Chen e Har-Peled em um PTAS para orientação no avião. É um problema de maximização.

Chandra Chekuri 17/10/11

Fizemos o upload de uma pré-impressão que trata dessa questão, ou seja, fornece um PTAS para TSP máximo de dispersão no caso euclidiano. arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: um PTAS para TSP de dispersão máxima euclidiana)

László Kozma

Fizemos o upload de uma pré-impressão que trata dessa questão, ou seja, fornece um PTAS para TSP máximo de dispersão no caso euclidiano. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: um PTAS para o TSP de dispersão máxima euclidiana)

László Kozma
fonte