Najdluzszy obwod lub najwieksze pole figury

Witam.
Problem: W zboirze punktow poszukuje figury o najdluzszym obwodzie lub najwiekszym polu. (wykorzystuje wszystkie punkty)

Moj wstepny algorytm:

1. Permutacja punktow
2. Dla kazdego przypadku sprawdzam czy kolejny odcinek punkt-punkt nie przecina sie z poprzednimi. Jesli tak - usuwam wariant, jesli nie - mam gotowa figure.
3. Licze obwod i powierzchnie dla kazdego "dobrego" wariantu
4. Sortuje po polu i po obwodzie

Gdybym mial do znalezienia tylko najwiekszy obwod, to moglbym zastanowic sie nad znalezieniem najdluzszych odcinkow punkt- punkt a nastepnie na sprawdzaniu czy istnieja figury zawierajace najwieksze odcinki.

Czy spotkaliscie sie juz gdzies z takim problemem (www, ksiazki)?
Co moglbym tu poprawic?

Pisałem taki program, który znajdował taką figurę ze zbioru punktów, która zawierała "w sobie" wszystkie inne punkty. Wydaje mi się, że to to samo ;). Ja miałem to oparte na równaniach prostych:

1. Połącz punkty prostą (każdy z każdym) i oblicz równanie prostej.
2. Podstaw kolejno wszystkie punkty pod x,y równania prostej.
3. Jeżeli równanie prostej < 0 punkt leży w środku figury -> ok
   jeżeli = 0, punkt leży na prostej -> też ok.
   jeżeli > 0 leży poza figurą, więc prosta jest do odrzucenia.

Na końcu zostają tylko proste (a dokładniej odcinki), które Ci ładnie zdefiniują figurę.
Trochę tu jest iteracji, więc nie jest to super wydajne, ale nie próbowałem optymalizować.
Działa to bez problemu dla 2D, dla n wymiarowej przestrzeni to już zabawa z macierzami.

PS. Pisałem z pamięci, jakby co to mogę sprawdzić później w kodzie.

Nie, ja musze stworzyc figure oparta na wszystkich punktach.
To co opisujesz to algorytm na "otoczke wypukla". O ile jest poprawny, nie wnikam.

Co znaczy "poszukuje figury o najdluzszym obwodzie lub najwiekszym polu" przecież to wzajemnie wykluczające się cele.
Czemu odrzucasz przecinanie się boków? Klepsydra zadana 4-ma punktami to też figura (o najdłuższych obwodzie) prostokąt przez te same punkty - największe pole.

Fakt, zle to sformulowalem.
Poszukuje dwoch figur ograniczonych tymi punktami. Jedna z najwiekszym polem, druga z najdluzszym obwodem.
Poniewaz punkty te ograniczaja figure, wiec odrzucam przeciecia bo te tworza nowe kupnkty ograniczajace.