Considere a matriz de pontos no espaço 2D, 3D, (4D ...) (por exemplo, nós demalha não estruturada ) Inicialmente, o índice de um ponto na matriz não está relacionado à sua posição no espaço. Em um caso simples, suponha que eu já conheça algum gráfico de conectividade de vizinho mais próximo.

Eu gostaria de algumas heurísticas que aumentem a probabilidade de que dois pontos próximos um do outro no espaço tenham índice semelhante (estariam próximos na matriz).

Entendo que a solução exata é muito difícil (talvez semelhante aProblema do vendedor ambulante ), mas não preciso de uma solução exata, apenas algo que aumente a probabilidade.

Minhas idéias sobre solução:

alguma solução ingênua seria como:

1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise)
   E_i = -Sum_k ( abs( index(i)-index(k) ) ) 
   where "k" are spatial nearest neighbors of "i" 
2. for pairs of points (i,j) which have low fitness (E_i,E_j) 
   try to swap them, 
   if fitness improves, accept

mas a implementação detalhada e sua otimização de desempenho não são tão claras.

Outra solução que não necessite de vizinhos mais próximos pré-computados seria baseada emLocality-sensitive_hashing

eu acho istopode ser um problema bastante comum e podem existir boas soluções, Não quero reinventar a roda.

Inscrição:

melhorar a localidade do cache, considerando que o acesso à memória geralmente é um gargalo da passagem de gráficopoderia acelerar a interpolação da grade não estruturada, mais especificamente procurar nós que estão próximos ao smaple (por exemplo, centros da função de base radial).