O que é essa estrutura / conceito de dados em que um gráfico de pontos define uma partição para um espaço

15

Encontrei um algoritmo para resolver um problema do mundo real e lembro-me de uma aula que fiz onde fiz algo muito semelhante para alguns para um problema de lição de casa. Se parece com isso

Basicamente, é um gráfico de pontos, e as linhas são desenhadas para serem equidistantes entre dois pontos. Ele forma uma partição perfeita, onde as linhas ao redor do ponto formam a forma da área mais próxima desse ponto. Isso soa um sino para alguém? Eu tive um tempo difícil pesquisando descrições e obtendo resultados. E não sei mais como descrevê-lo. Espero que a imagem ajude.

Brian
fonte
Visto 1667 vezes desde ontem? SE está sendo hackeado?
HEKTO 23/01/19
@HEKTO foi exibido como uma das "Perguntas sobre a rede quente".
John L.

Respostas:

31

O que você descreveu é o diagrama de Voronoi .

Aqui está um trecho da Wikipedia.

Imagem do diagrama de Voronoi da Wikipedia

No caso mais simples, mostrado na primeira figura, recebemos um conjunto finito de pontos no plano euclidiano. Nesse caso, cada site é simplesmente um ponto, e sua célula Voronoi correspondente consiste em todos os pontos do plano euclidiano cuja distância a é menor ou igual à sua distância a quaisquer outros pontos. Cada célula é obtida a partir da interseção de meios espaços e, portanto, é um polígono convexo. Os segmentos de linha do diagrama de Voronoi são todos os pontos no plano que são equidistantes dos dois locais mais próximos. Os vértices de Voronoi (nós) são os pontos equidistantes de três (ou mais) locais.p1 1,,pnpkRkpk

John L.
fonte
4
+1. Abstive-me de mencioná-las e fui para implementações porque lembro que meus professores as mencionaram com uma nota de rodapé de que os diagramas de Voronoi são computacionalmente bastante complexos para serem implementados em dimensões mais altas. Portanto, implementações simples de kNN fazem o trabalho muito melhor. No entanto, a condição de que "as linhas são desenhadas para serem equidistantes entre dois pontos" pode não ser cumprida.
Sagnik 22/01/19