Algoritem: Se da ločiti dve množici točk s premico v O(n)?

Moja ideja je poiskat točke, ki ležijo na robu teh množic (tvorijo konveksno ogrinjačo/convex hull) in potem preverjat, če kaka točka iz prve množice pade v drugo oz. če se ogrinjači sekata/dotikata. Če se ne, premica obstaja.
Output-sensitive algoritmi za convex hull poberejo O(k*n), kjer je k število točk na robu ogrinjače, tisti lažji za implementacijo (graham scan) pa O(n log(n)), zahtevnosti algoritma za iskanje preseka dveh konveksnih poligonov pa ne poznam, ampak pomojem zna bit dovolj hiter.

Precej verjetno pa obstaja kak boljši način...

Živijo,

Samo malo brainstorminga, ko sem prebral temo.

Mogoče je ideja s konveksno ogrinjačo/lupino kar malce preveč, glede na to da iščeš premico, ki seka celoten prostor. To namreč število primerov, ki se dajo ločiti precej zmanjša.

Lahko bi povedal tudi kaj predstavlja n v časovni kompleksnosti O(n), predvidevam da |M| + |R|?

Še ena ideja, ki mi je prišla na misel pa je da (vsaj kot si formuliral vprašanje) ne rabiš poiskati te premice, temveč zgolj preveriti ali kakšna takšna obstaja. Morda se na prvi pogled problema zdita enaka, vendar je problem obstoja zagotovo lažji oziroma največ enako težak kot problem iskanja določene premice.

Ne bi tako kompliciral, če ne bi šlo za nalogo iz časovne zahtevnosti, kjer pač vsaka zanka šteje :)

Kaj pa vem :) To je bil samo osnutek za nadaljnje razmisljanje ...

Sem pa nasel eno stran, kjer so tangente med dvema poligonoma in algoritmi. Ti bi rabil Tll ali Trr: Link