On 12.02.2016 14:49, slawek wrote:
> On Wed, 10 Feb 2016 01:46:57 -0800 (PST), "M.M." <m...@g...com>
> wrote:
>> Ma ktoś ochotę zaimplementować ten algorytm?
>
> Miałbym, ale mam teraz dużo innych pilnych spraw.
>
> Wydaje mi się że można zrobić algorytm O(N log N) i to dość prosty:
>
> 1. Rzutujemy na przestrzenie jednowymiarowe.
> 2. Sortujemy.
> 3. Rozwiązujemy te problemy 1D.
> 4. Odrzucamy z wielowymiarowego problemu punkty niezgodne z
> rozwiązaniami 1D.
> 5. Wykorzystujemy inteligentnie pomysł z konstrukcją okręgu przez trzy
> punkty. Sprawdzamy tylko te które są skrajne w 1D.
>
> Najdłużej będzie trwało sortowanie. Kwestia otwarta: czy istnieje jakiś
> patologiczny przypadek, że się nie uda.

A B

C

Odległość AB = 1
odległosc BC = 1.4...1.42

Rzut na odrzucił A. Rozwiązaniem jest {B,C}
rzut na y odrzucił C, Rozwiązaniem jest {A,B}

Nie widzę, jak ten alborytm teraz zszywa rozwiązanie.

> Ale ogólnie powinno działać.

To szukasz algorytmu, czy heurystyki?

pzdr
bartekltg