curs8p2

GeneralitatiAlgoritmul lent

Grahams scan

Acoperiri convexe

Mihai-Sorin Stupariu

Curs 8 (II), Sem. I, 2011-2012

Mihai-Sorin Stupariu Acoperiri convexe


Grahams scan

Multimi convexe

I Conceptul de multime convexa:O multime M Rm este convexa daca oricare ar fi p, q M,segmentul [pq] este inclus n M.

I Problematizare:Multimile finite cu cel putin doua elemente nu sunt convexe necesara acoperirea convexa.



Grahams scan

Acoperire convexa a unei multimi finite P (formal)

I Cea mai mica (n sensul incluziunii) multime convexa carecontine P.

I Intersectia tuturor multimilor convexe care contin P.I Multimea tuturor combinatiilor convexe ale punctelor din P.



Grahams scan



I Intersectia tuturor multimilor convexe care contin P.

I Multimea tuturor combinatiilor convexe ale punctelor din P.



Grahams scan



I Intersectia tuturor multimilor convexe care contin P.I Multimea tuturor combinatiilor convexe ale punctelor din P.



Grahams scan

Acoperire convexa a unei multimi finite P (practic)

I De fapt, daca P este finita, acoperirea sa convexa, Conv(P)este un poligon convex.

I Problema:Cum determinam, algoritmic, varfurile acestui poligon?

I Conventie: Sensul de parcurgere a frontierei este cel al acelorde ceasornic.



Grahams scan

Algoritmul lent: idee de lucru

I Sunt considerate muchiile orientate.

I Q: Cum se decide daca o muchie orientata fixata este pefrontiera?

I A: Toate celelalte puncte sunt n dreapta ei.



Grahams scan

Algoritmul lent: idee de lucru

I Sunt considerate muchiile orientate.I Q: Cum se decide daca o muchie orientata fixata este pe

frontiera?

I A: Toate celelalte puncte sunt n dreapta ei.



Grahams scan

Comentarii

I Complexitatea: O(n3).

I Tratarea cazurilor degenerate: poate fi adaptat.I Robustetea: datorita erorilor de rotunjire este posibil ca

algoritmul sa nu returneze o lista coerenta de muchii.



Grahams scan

Comentarii

I Complexitatea: O(n3).I Tratarea cazurilor degenerate: poate fi adaptat.

I Robustetea: datorita erorilor de rotunjire este posibil caalgoritmul sa nu returneze o lista coerenta de muchii.



Grahams scan

Comentarii

I Complexitatea: O(n3).I Tratarea cazurilor degenerate: poate fi adaptat.I Robustetea: datorita erorilor de rotunjire este posibil ca

algoritmul sa nu returneze o lista coerenta de muchii.



Grahams scan

Grahams scan: idee de lucru

I Punctele sunt mai ntai sortate si renumerotate lexicografic.

I Algoritmul este de tip incremental, punctele fiind adaugateunul cate unul, fiind apoi eliminate anumite puncte.

I Q: Cum se decide daca trei puncte sunt varfuri consecutiveale acoperirii convexe?

I A: Se efectueaza un viraj la dreapta n punctul din mijloc.



Grahams scan

Grahams scan: idee de lucru

I Punctele sunt mai ntai sortate si renumerotate lexicografic.I Algoritmul este de tip incremental, punctele fiind adaugate

unul cate unul, fiind apoi eliminate anumite puncte.

I Q: Cum se decide daca trei puncte sunt varfuri consecutiveale acoperirii convexe?

I A: Se efectueaza un viraj la dreapta n punctul din mijloc.



Grahams scan

Comentarii

I Complexitatea: O(n log n).

I Tratarea cazurilor degenerate: corect.I Robustetea: datorita erorilor de rotunjire este posibil ca

algoritmul sa returneze o lista eronata (dar coerenta) demuchii.



Grahams scan

Comentarii

I Complexitatea: O(n log n).I Tratarea cazurilor degenerate: corect.

I Robustetea: datorita erorilor de rotunjire este posibil caalgoritmul sa returneze o lista eronata (dar coerenta) demuchii.



Grahams scan

Comentarii

I Complexitatea: O(n log n).I Tratarea cazurilor degenerate: corect.I Robustetea: datorita erorilor de rotunjire este posibil ca

algoritmul sa returneze o lista eronata (dar coerenta) demuchii.


GeneralitatiAlgoritmul "lent"Graham's scan

curs8p2

Documents