Inserir um ponto em uma região 2D finito com distância máxima de pontos existentes

Question

Eu tenho um conjunto de 2D pontos dentro de uma região finita do espaço 2D (digamos que um retângulo alinhado ao mundo para manter as coisas simples por agora). O que seria uma maneira extremamente eficiente para inserir um novo ponto no conjunto que tem uma distância relativamente grande para seu novo vizinho mais próximo?

Eu poderia lentamente construir uma triangulação de Delaunay e limitar a pesquisa apenas os maiores triângulos, mas eu estava esperando que alguém tem uma idéia diferente (melhor).

Goodwill, David

---

Editar:

esqueci de mencionar que eu preciso fazer isso milhares de vezes, cada vez que tomar todos os pontos anteriores em conta. Eu estou procurando um algoritmo que não abrandar para um rastreamento como meu conjunto de pontos cresce.

Answer 1

Use o Bowyer-Watson ou outro algoritmo incremental para manter o diagrama de Voronoi. Os vértices do diagrama de Voronoi são pontos candidatos, manter todos os pontos do candidato em uma fila de prioridade ordenada pela distância para os pontos de origem. Isso deve ser bastante rápido, e melhor (pelo menos, melhor em cada etapa).

Você estava procurando por algo mais rápido e menos ideal?