Dividindo um conjunto de pontos em dois subconjuntos ideais

9

Quero dividir um conjunto de pontos em dois subconjuntos de tamanhos iguais, de modo que a soma dos quadrados dentro do cluster seja minimizada. Podemos assumir que os pontos estão no espaço euclidiano bidimensional. Espero algo mais rápido do que um algoritmo de agrupamento geral k-means, dado que k = d = 2. Alguém pode me apontar na direção de um bom algoritmo para isso?

Uma solução exata não é necessária se tivermos uma boa aproximação.

Obrigado!

Andrew Baker
fonte

Respostas:

10

kO(n4/3registron)knk=n/2] Depois de ter todas as partições possíveis, basta verificar cada uma delas. Usando truques padrão, isso pode ser feito em tempo constante para cada partição.

kk=n/2

kO(ϵ-2registron)n

http://sarielhp.org/p/03/kcoreset/

Sariel Har-Peled
fonte