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. Ale ogólnie powinno
działać.