Selecionando a maioria dos pontos dispersos de um conjunto de pontos

15

Existe algum algoritmo (eficiente) para selecionar um subconjunto de pontos de um conjunto de pontos ( ), de modo que eles "cubram" a maior parte da área (em todos os subconjuntos possíveis de tamanho )?MM < N MNM<NM

Presumo que os pontos estejam no plano 2D.

O algoritmo ingênuo é simples, mas proibitivo em termos de complexidade de tempo:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Estou procurando um método mais eficiente ou até aproximado.

Exemplo, aqui está um plano com alguns pontos aleatórios:

insira a descrição da imagem aqui

Para , espero selecionar pontos como estes:M=5

insira a descrição da imagem aqui

Observe que os pontos selecionados (vermelho) estão espalhados por todo o plano.

Encontrei um artigo " SELECIONANDO EFICIENTEMENTE KEYPOINTS DISTRIBUÍDO ESPACIALMENTE PARA O RASTREIO VISUAL ", relacionado a esse problema. No entanto, isso pressupõe que os pontos são ponderados.

Libor
fonte
2
Para o caso veja isso no StackOverflow: Algoritmo para encontrar pontos mais distantes - melhores que O (n ^ 2)? . M=2
hardmath
Infelizmente, é geralmente em torno de 1500-5000 e é 10-50. MNM
Libor
São e N ambos fixos, ou está variando M , bem como (por exemplo, porque quer para maximizar a média das distâncias, em cujo caso o aumento M ainda pode produzir um decréscimo)? MNMM
Wolfgang Bangerth
11
Eu suspeito fortemente que isso seja difícil para o NP. Assemelha-se muito a um problema de clique de peso máximo, onde o peso da aresta entre dois vértices é a distância euclidiana entre eles. (Eu acredito que há heurísticas praticamente eficazes conhecidos para max-clique não tenho certeza quais são..)
tmyklebu
11
@hardmath Desculpe, isso foi um erro de digitação. Tentei ilustrar o que preciso alcançar. O problema vem da extração de recursos de imagem, onde eu preciso obter apenas alguns recursos de pontos, mas tê-los espalhados por toda a imagem, porque eles são usados ​​para estimativa de transformação e, quando dispersos espacialmente, a estimativa é mais estável. Talvez "entropia" seja uma medida melhor - eu gostaria de escolher pontos modo que eles estejam em todo lugar, como um gás no estado máximo de entropia. Por outro lado, estou tentando evitar que os pontos selecionados sejam agrupados. M
Libor

Respostas:

11

Aqui está uma solução aproximada. Como N é tão grande e M é tão pequeno, que tal o seguinte:

  1. Calcular o casco convexo de N
  2. Selecione até M pontos no casco que atendem aos seus critérios de distância máxima.
  3. Se a Etapa 2 deixar você com menos de M pontos, selecione 1 ponto no interior que maximize sua distância dos pontos selecionados anteriormente.
  4. Repita a Etapa 3 até que o número de pontos selecionados seja M

A intuição por trás disso é que, como N >> M , e você deseja que os pontos sejam o mais distantes possível, eles provavelmente estarão próximos das bordas dos dados; portanto, é melhor começar com o casco e, em seguida, iterativamente. trabalhar o seu caminho a partir daí.

Além disso, começando com o casco, você reduz sua pesquisa inicial de N para N 1/2 .


ATUALIZAR

Se as etapas 3 e 4 acima estiverem demorando muito (já que você está testando iterativamente o interior do seu conjunto de dados), me ocorreram mais duas idéias para acelerar o seu problema.

  1. Pesquisa Aleatória : Digamos que você encontrou pontos P no casco na Etapa 2. Em seguida, desenhe aleatoriamente pontos M - P a partir do interior. Selecione o melhor conjunto após X testes.
  2. Recozimento simulado : calcule a menor caixa delimitadora que cobre seu conjunto de dados (não precisa estar alinhado com os eixos, pode ser inclinado). Em seguida, defina um conjunto de M pontos de grade distribuídos uniformemente nessa caixa delimitadora. Observe que esses pontos não coincidem necessariamente com nenhum dos pontos do conjunto de dados. Em seguida, para cada ponto da grade, encontre os k- vizinhos mais próximos no seu conjunto de dados. Percorra todas as combinações M x k e selecione aquela que atenda aos seus critérios de distância máxima. Em outras palavras, você está usando a grade inicial como um bootstrap para encontrar uma boa solução inicial.
dpmcmlxxvi
fonte
Obrigado. Talvez um tenha formulado a pergunta de maneira errada. Estou buscando um conjunto de pontos que "cubram" a maior parte da área. Eu pensei que apenas os critérios de distância são suficientes, mas parece que algo mais precisa ser adicionado.
Libor
M
11
Talvez uma maneira mais formal de expressar seu problema seja o desejo de um mosaico de tamanho M que cubra N e minimize a área média da faceta do mosaico? Minimizar as áreas das facetas parece ser uma maneira de espalhar os pontos e garantir que eles não se juntem.
dpmcmlxxvi
Sim. Eu queria evitar o uso da grade, porque se os pontos puderem ser agrupados acidentalmente em torno das linhas da grade, eles serão agrupados na seleção.
Libor
O único problema com o seu algoritmo guloso que você mencionou é que ele será muito sensível ao ponto inicial da semente. Os algoritmos de crescimento de sementes (onde você começa de dentro para fora) têm esse problema. A abordagem do casco que mencionei provavelmente será mais estável, pois funciona de fora para dentro.
dpmcmlxxvi
6

NM

MM

M1 1M=3,4,5

M=31 1M=4M=51 1

Se desejamos evitar a seleção predominante de pontos na periferia, um objetivo diferente pode ser útil. A maximização da distância mínima entre pontos é esse critério. Problemas relacionados foram abordados no StackOverflow , na Computer Science SE , no Math.SE e no MathOverflow .

MDMD

hardmath
fonte
1

OK, então você deseja selecionar M pontos de um determinado conjunto de N pontos no plano euclidiano, para que a soma das distâncias em pares dos pontos selecionados seja máxima, correto?

O algoritmo de busca local padrão é bastante rápido e oferece uma boa aproximação. O tempo de execução é linear em N e quadrático em M. Sua taxa de aproximação é de 1 a 4 / M. Isso significa que a proporção melhora à medida que M aumenta. Por exemplo, para M = 10, obtém 60% do valor ideal e, para M = 50, obtém 92% do valor ideal.

O algoritmo também funciona para espaços euclidianos de dimensão geral. Nesse caso, o problema é difícil para o NP. Mas no avião, não se sabe se é NP-difícil.

A fonte é este artigo . Espero que isto ajude! Best, Alfonso


Alfonso
fonte
11
Eu já resolvi isso usando o algoritmo "Supressão por cobertura de disco" do artigo "Selecionando com eficiência pontos-chave distribuídos espacialmente para rastreamento visual" 2011 18ª Conferência Internacional da IEEE sobre Processamento de Imagens. IEEE, 2011
Libor
11
Alfonso, explique sua afiliação ao artigo sugerido.
nicoguaro
0

Uma solução é:

  • O(n)

  • Torne M artificial mesmo pontos distribuídos dentro deste retângulo delimitador, alguns M são mais difíceis que outros. No seu caso, quatro nos cantos do retângulo e um no centro

  • O(n(euog(n)))

  • O(m(euog(n)))

O(n(euog(n)))MN

Jan Hackenberg
fonte