Envelope

[•crushack]

Salut, stie cineva unde gasesc informatii despre algoritmul de Envelope ? ( Upper-Envelope , Lower-Envelope ) Tocmai am dat peste termen si mi se pare interesant

[•Oancea.Catalin]

Te referi la "Upper Envelope of Segments"?

[•gabitzish1]

Cauta sa vezi daca gasesti descrierea solutiei la problema Forum de la runda 1 .campion 2009.

[•crushack]

Ma refer la Envelope in general .

Poi de la problema aia am aflat de asta si m-a lasat rece   ca nu explica cum se face envelope

[•MciprianM]

Dupa o cautare pe google am gasit destul de multe rezultate. Gandeste-te la o multime de curbe(marcate intr-un sistem de coordonate) si ca aceste curbe reprezinta niste ziduri inalte dupa care nu poti vedea nimic. Apoi gandeste-te ca te plimbi pe axa Ox de la minus infinit la plus infinit si te uiti pe o directie paralela cu Oy, sensul inspre y. Toate punctele pe care le vezi formeaza lower envelope. Pentru upper envelope, faci ceva similar pe o dreapta paralela cu oX, aflata undeva la infinit, doar ca de data asta te uiti in jos.
Putin formal lower envelope L = { (x,y)|x in R && (x,y) e pe o curba din cele date si y minim }
Edit: Si un link: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Envelope_2/Chapter_main.html

[•crushack]

Aaa am inteles.
Da tot nu stiu cum s-o fac in O(1) adica, sti vre-un site sa spuna cum se foloseste?

[•CezarMocan]

Problema Forum se poate rezolva si cu Diagrame Voronoi (trebuie sa gasesti celula Voronoi a punctului (0, 0) si apoi pentru fiecare query sa verifici daca punctul se afla in celula). Am prezentat asta la lot, daca vrei mai multe detalii / sursa spune.

[•crushack]

Poti sa clarifici , pls ?
Cum gasesti elementele dominante ( ca in problema terenuri ) ale punctului (0,0) ?

[•CezarMocan]

Citeste putin aici, explica bine principiul dualitatii si diagramele Voronoi. Pe scurt, celula Voronoi a punctului (0, 0) reprezinta locul geometric al punctelor care sunt mai apropiate de el decat de celelalte N puncte, si are forma unui poligon convex (posibil deschis). Se poate determina in O(N log N) folosind dualizarea si o infasuratoare convexa. Sper sa iti fie de folos, daca mai ai intrebari nu ezita sa le pui!