Największy wypukły wielokąt ortagonalny

Witam, od kilkudziesieciu godzin próbuję stworzyć algorytm do swojego projektu na Analizę Algorytmów i mówiąc delikatnie na razi odbijam się od ściany.

W ogólności problem jest taki jak w temacie. Jest obszar w wymiarach [0,a] x [0,b] a wewnątrz jest n punków(współrzędne dodatnie, całkowite). Znaleziony wielokąt nie może mieć w środku żadnych punków.

wielokąt jest ortagonalny jeśli jego wszystkie krawędzie są równoległe do którejś osi układu współrzędnych, zaś wielokąt ortagonalny jest wypukły jeśli nie istnieje żadna prosta rónoległa do osi układu wsp. mająca więcej niż jeden odcinek wspólny z wielokątem.

Czyli dla przykładu z czegoś takiego: powstanie takie coś:

Mój aktualny pomysł, a raczej zalążek pomysłu jest taki:

1. Posortować punkty według x-ów(i y jeśłi x równe)
2. Omiataniem "przemielić" zbiór.

No i z tym mieleniem mam problem. Mam wrażenie, że tak naprawdę każdy(a przynajmniej większość punktów) na lini omiatającej poprzedzającej aktualną może mi napsuć i generować nowe kształty(nie jestem przekonany, czy to zdanie jest zrozumiałe ^^). Generalnie chodzi o to, że na razie każdy mój pomysł ma kosmiczną złożoność obliczeniową, co sugeruje, że mój tok rozumowania nie jest najlepszy/poprawny.

Ja za to nijak nie rozumiem dlaczego

jest uznany przez Ciebie za wypukły :].

Według klasycznej definicji, oraz wg. Twojego zaś wielokąt ortagonalny jest wypukły jeśli nie istnieje żadna prosta rónoległa do osi układu wsp. mająca więcej niż jeden odcinek wspólny z wielokątem taki nie jest.
Intuicyjnie wypukły wielokąt to taki którego wszystkie kąty wewnętrzne < 180 stopni.

Pytam najpierw, bo nie ma co myśleć nad rozwiązaniem dopóki się nie zrozumie problemu.

Intuicyjnie to mi też się ciągle wydaje, że wypukły to taki, który ma kąty wew < 180 stopni, ale taką definicję jak podałem mam w zadaniu. No, żeby być dokładnym to napisane jest: że wieloką† ortagonalny jest wypukły jeśli dowolna prosta równoległa do osi ma z wielokątem ma co najwyżej jeden odcinek wspólny. Ale to chyba to samo :)(ręki nie dam).

Ja na tym drugim rysunku nie mogę znaleźć takiej prostej, która ma więcej niż jeden odcinek wspólny z wielokątem.

Ja na tym drugim rysunku nie mogę znaleźć takiej prostej, która ma więcej niż jeden odcinek wspólny z wielokątem.

To chyba są dwa wspólne odcinki na prostej równoległej do osi układu?

Tak na moje oko prawidłową odpowiedzią będzie

Proponuję przećwiczyć. Sposób rysowania dużo podpowiada, jak mógłby algorytm wyglądać...