Na ograniczonej płaszczyźnie mamy zadane n punktów. Punkty mogą się
powtarzać, to znaczy mogą istnieć dwa o takich samych współrzędnych,
wtedy liczone są podwójnie a nie pojedynczo.
Wybieramy inne m punktów które nie mogą się powtarzać, gdzie m dużo
mniejsze od n.
Siatkę Voronoi definiujemy jako te punkty płaszczyzny, które są
najbliższe jednemu z tych m.
Teraz, jak wybrać te m punktów, aby sumaryczna odległość punktu ze
zbioru punków zadanych do najbliższego z tych m, była najmniejsza. (czy
też suma kwadratów odległości)
Czy jest jakiś algorytm na to? Czy da się rozwinąć na 3 wymiary?

do góry

On 19.07.2015 10:54, Borneq wrote:
> Na ograniczonej płaszczyźnie mamy zadane n punktów. Punkty mogą się
> powtarzać, to znaczy mogą istnieć dwa o takich samych współrzędnych,
> wtedy liczone są podwójnie a nie pojedynczo.
> Wybieramy inne m punktów które nie mogą się powtarzać, gdzie m dużo
> mniejsze od n.
> Siatkę Voronoi definiujemy jako te punkty płaszczyzny, które są
> najbliższe jednemu z tych m.
> Teraz, jak wybrać te m punktów, aby sumaryczna odległość punktu ze
> zbioru punków zadanych do najbliższego z tych m, była najmniejsza. (czy
> też suma kwadratów odległości)


Chyba po prostu szukasz tego.
https://en.wikipedia.org/wiki/K-means_clustering
Jeśli punktów jest dużo, przydadzą sie rozwiązania przybliżone.

Jest kupa gotowców.

> Czy jest jakiś algorytm na to? Czy da się rozwinąć na 3 wymiary?

Tak. Ale wymiar mnoży się przez liczbę punktów, a wszytko to ląduje
w wykładniku złożoności ;-)

do góry