Como calcular com eficiência o ponto mais isolado?

8

Dado um conjunto finito de pontos em , como podemos calcular eficientemente um "ponto mais isolado" ? $S$ $\mathbb R^d$ $x\in S$

Definimos um "ponto mais isolado" por $x$

x = \arg max_{p \in S} min_{q \in S ∖ {p}} d (p, q)

$x = \arg\max_{p \in S} \min_{q \in S \setminus \{p\}} d(p,q)$

(Usei a notação $x=\arg\min$ , mesmo que não seja necessariamente única. Aqui $d$ indica a distância euclidiana.) Portanto, em outras palavras, estamos procurando um ponto com a maior distância para o vizinho mais próximo.

Um algoritmo ingênuo estaria computando todas as distâncias aos pares, encontrando o vizinho com a menor distância para cada ponto e, em seguida, encontrando o máximo deles. São operações $O(n^2)$ , mas podemos fazer melhor que isso?

algorithms graph-theory computational-geometry nearest-neighbour flawr
fonte

Eu sugiro olhar para estruturas de dados para pesquisa de vizinhos mais próximos . Suspeito que eles possam ser adaptados para ajudar a resolver esse problema com mais eficiência do que o método ingênuo.

DW

@DW Obrigado pela recomendação. Tentei examinar o kd-trees, mas não encontrei uma maneira mais eficiente de resolver esse problema.

flawr

1

Use qualquer algoritmo para todos os vizinhos mais próximos ; então você pode resolver trivialmente seu problema. Esse algoritmo encontra, para cada ponto de dados, seu vizinho mais próximo. O ponto mais isolado é aquele cujo vizinho mais próximo está mais distante; portanto, depois de resolver todos os vizinhos mais próximos, você pode encontrar o ponto mais isolado com uma simples varredura linear.

Aparentemente, todos os vizinhos mais próximos podem ser encontrados no tempo ; veja as referências na Wikipedia. Ou, se você quiser algo para implementar, escolha qualquer estrutura de dados para os vizinhos mais próximos e, para cada ponto , encontre o vizinho mais próximo. $O(n \log n)$ $p$

DW
fonte

0

Conforme sugerido nos comentários, eu pesquisaria as consultas de vizinhos mais próximos.

Fazer uma consulta NN por ponto deve estar na ordem de portanto já é melhor que a solução ingênua. $O(n* log (n))$

Você pode melhorar ainda mais isso adicionando um parâmetro à consulta NN que contém a distância vizinha mais próxima do ponto mais isolado que você encontrou até agora. Você pode abortar qualquer consulta NN assim que encontrar um ponto mais próximo que . Isso deve acelerar bastante a sua pesquisa. $d_{max}$ $d_{max}$

Btw, as pessoas geralmente sugerem KD-Trees para NN-Search. As árvores KD são muito fáceis de implementar, mas, na minha experiência, escalam consistentemente menos bem com dimensões mais altas do que outras árvores. Para ou mais, eu recomendaria usar uma R-Tree, como R * Tree (R-Star-Tree), X-Tree ou R-Tree carregada por STR ou uma PH-Tree (que é mais parecida com uma quadtree bit a bit). $d > 10$

TilmannZ
fonte

Como calcular com eficiência o ponto mais isolado?

Respostas: