» »

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

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

AndyS ::

Imamo množici točk v ravnini. Recimo točkam v prvi Mi v drugi Ri.
Torej, rabil bi idejo za algoritem, ki bi ugotovil ali se da ločiti ti dve množici s premico, v času O(n).

Hvala za ideje.
LP

HairyFotr ::

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...

Zgodovina sprememb…

Genetic ::

1. Poisci sredisci obeh mnozic Sm in Sr (Sm.x = sum(Mi.x)/card(M), Sm.y = sum(Mi.y)/card(M), podobno za Sr)
2. Doloci premico, ki gre skozi sredisci Sm in Sr: pS
3. V smeri Sm proti Sr poisci dve maximalno oddaljeni tocki iz M: M1 in M2 (skalarni produkt SmSr*SmMi je najvecji)
4. Doloci premico skozi M1 in M2: pM
5. Ce sta Sm in Sr na istem bregu premice pM, koncaj: ni mogoce dolociti premice
6. Drugace: v smeri Sr proti Sm poisci maximalno oddaljeno tocko iz R: R1
7. Ce sta Sm in R1 na istem bregu premice pM ali pa R1 lezi na premici pM, koncaj: ni mogoce dolociti premice
8. Ce prides do te tocke, potem je resitev kar premica pM (ki jo po potrebi malo premaknes v smeri SmSr, da se nedotika nobene od tock M1, M2, R1)

incognito ::

Ž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 :)

AndyS ::

n je moč obeh množic skupaj ja.

Jah z lupino verjetno ne bi šlo ker rabimo nlogn, da jo izračunamo.

Ideja od genetica mi je zelo všeč. Ne razumem pa najbolj 3. točke.

3. V smeri Sm proti Sr poisci dve maximalno oddaljeni tocki iz M: M1 in M2 (skalarni produkt SmSr*SmMi je najvecji)

Jaz sem potem kar vzel najbolj oddaljeno točko iz M na levo in najbolj oddaljeno iz M na desno glede na premico pS. Je to prav?

Genetic ::

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

Zgodovina sprememb…

  • spremenil: Genetic ()

Rokm ::

Pomoje je tukaj najboljše, da uporabiš dualnost, torej točke preslikaš v premice in premice v točke. Točka T(a,b) gre v premico T* y = a*x + b, premica l y=a*x+b pa v točko l*(a,b). Če je točka T v osnovnem svetu na premico l, je potem tudi točka l* nad premico T*.

Tako sedaj dobiš množici M* in R*, ki imata vsaka po nekaj premic. In če zdaj te premice vzameš za pogoje(seveda moraš upoštevati, da jih lahko razdeli tako da je ena spodaj in druga zgoraj ali obratno) linearnega programiranja lahko v O(n) ugotoviš ali obstaja neka rešitev za te pogoje.

Zgodovina sprememb…

  • spremenil: Rokm ()


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Linearne funkcije

Oddelek: Šola
61174 (873) lebdim
»

Vektorji

Oddelek: Šola
102875 (2583) lebdim
»

Geometrijska konstrukcija

Oddelek: Šola
453665 (3665) euler
»

Matematična težava

Oddelek: Šola
139227 (9018) bosstjann
»

pomoč pri linearni algebri

Oddelek: Šola
62999 (2850) whatever

Več podobnih tem