W dniu 2014-07-02 00:30, bartekltg pisze:
> http://en.wikipedia.org/wiki/Maximum_disjoint_set
>
> Zastępujesz punkty kolami o srednicy równej minimalnemu dystansowi.
>
> Nadal NP-trudne.

A to coś zmienia? Ja zastępuję prostokąty różnych wielkości otaczające
elipsoidalne kształty punktami w ich środku. A odległość traktuję
binarnie - bliżej/nie bliżej

> Najprostszy zachłanny będzie liniowy względem rozmiaru grafu (V+E).

Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
przeszkadza, ale w jaki sposób uzyskać czas liniowy?
Pierwszą częścią jest w ogóle uzyskanie grafu - tu biorę odległość każdy
z każdym, choć nie ma sensu brać odległości dwóch odległych punktów.
Potem jest właściwy algorytm. Liczba krawędzi wychodząca z każdego
wierzchołka jest mała w porównaniu z liczbą wierzchołków - mniejsza niż
pierwiastek, raczej kilka. Ale algorytm który stosuję jest kwadratowy,
ponieważ jedno szukanie maksymalnego wierzchołka jest liniowe -
przelatuje przez wszystkie wierzchołki, choć wiele ma po tyle samo krawędzi.