Selecionando a maioria dos pontos dispersos de um conjunto de pontos

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 )?$M$M < N $N$$M < N$$M$

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:

Para , espero selecionar pontos como estes:$M=5$

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.

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.

$N$$M$

$M$$M$

$M$$1$$M=3,4,5$

$M=3$$1$$M=4$$M=5$$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 .

$M$$D$$M$$D$

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

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(log(n)))$

• $O(m(log(n)))$

$O(n(log(n)))$$\sqrt{M} \in \mathbb{N}$