Poligon3
Vom fixa pe rând fiecare punct din cele N date ca cel mai din stânga şi, în caz de egalitate, cel mai de sus punct ce poate fi pe poligon. După ce am fixat un anume punct de referinţă, ne mai interesează doar punctele cu absicsa strict mai mare sau cu abscisa mai mare sau egală şi ordonata strict mai mică ca a punctului fixat. Notăm punctul de referinţă cu 0. Sortăm punctele rămase în funcţie de panta segmentului pe care îl formează cu punctul de referinţă. Vom parcurge punctele rămase în această ordine şi folosind metoda programării dinamice vom construi o matrice C[i][j] = aria maximă a unui poligon care are ultimele două vârfuri în punctele j şi i. Recurenţa este C[i][j] = max{C[j][k] + Arie(0, i, j) | i, j, k păstrează forma convexă a poligonului şi triunghiul (0, i, j) nu conţine nici un alt punct în interior}. Testul de păstrare a convexităţii este explicat pe larg în acest articol. Verificarea ca triunghiul 0, i, j să nu conţină nici un alt punct se poate face in O(1) cu ajutorul unei preprocesari, conducând la o complexitate totală de O(N4).
Pentru a obţine complexitatea O(N3), vom modifica semnificaţia matricii astfel: C[i][j] = $ aria maxima a unui poligon ce are ultimul vârf în punctul $i şi penultimul vârf în unul dintre punctele dintre 1 şi j. Având un punct i fixat ca ultimul vârf al poligonului până în momentul respectiv, vom determina acele puncte j pentru care triunghiul (0, i, j) nu conţine nici un punct în interior. Punctul i-1 se află mereu printre aceste puncte j, deoarece este imposibil să existe vreun punct în triunghiul (0, i-1, i) din cauza sortării iniţiale. Apoi vom determina restul punctelor j cu o parcurgere în ordine inversă şi bazându-ne pe observaţia ca următorul punct j pe care îl vom determina va verifica testul de păstrare al convexităţii relativ la punctul i şi la ultimul punct de tip j pe care l-am determinat pâna acum. Punem toate aceste puncte j in multimea s în ordinea sortării (sau în ordinea inversă determinării lor). Recurenţa devine C[i][sk] = max{C[i][sk-1], C[sk][sk-1] + Arie(0, sk, i)}.
