Jak znaleźć prostokąt o maksymalnym polu powierzchni wewnątrz wypukłego wielokąta?

W tym poście szukamy algorytmów / pomysłów na znalezienie prostokąta o maksymalnej powierzchni wewnątrz wypukłego wielokąta .

Na poniższym rysunku liczby oznaczają obszary dopasowanych prostokątów. Jak pokazano pożądany prostokąt może różnić się w każdym wymiarze i może być pod dowolnym kątem.

Edytować:

Nie mamy żadnego jasnego pojęcia, jak poradzić sobie z wymienionym problemem, dlatego zapytaliśmy tutaj. Niemniej jednak domyślamy się , że prostokąt o maksymalnym polu powierzchni może być jednym z tych, które mają jedną krawędź wyrównaną na (niekoniecznie tej samej długości krawędzi oczywiście) krawędzi wielokąta.

Niektóre notatki są zbyt duże, aby można je było wstawić w komentarz (choć nie sugeruje to oczywistego algorytmu):

Linia dziurkowania (EDYCJA) : Przynajmniej dwa wierzchołki prostokąta o maksymalnej powierzchni muszą leżeć na granicy wielokąta (tj. Wzdłuż krawędzi lub na wierzchołku). A jeśli prostokąt o maksymalnej powierzchni nie jest kwadratem, co najmniej trzy wierzchołki muszą leżeć na granicy wielokąta.

Udowodniłem to sobie w czterech krokach:

Uwaga 1 : Przynajmniej jeden wierzchołek prostokąta o maksymalnej powierzchni zawsze będzie leżał na granicy wielokąta. Jest to dość oczywiste, ale dowód może być następujący (sprzeczność): Załóżmy, że masz „maksymalny” prostokąt bez wierzchołka na granicy wielokąta. Oznacza to, że wokół każdego z jego wierzchołków będzie przynajmniej trochę miejsca. Abyś mógł nieco rozszerzyć swój prostokąt, co jest sprzeczne z jego maksymalnością.

Uwaga 2 : Przynajmniej dwa wierzchołki prostokąta o maksymalnej powierzchni zawsze będą leżały na granicy wielokąta. Dowód może wyglądać następująco (znowu z powodu sprzeczności): Załóżmy, że masz „maksymalny” prostokąt z tylko jednym wierzchołkiem na granicy (gwarantowana przez uwagę nr 1). Rozważ dwie krawędzie, które nie sąsiadują z tym wierzchołkiem. Ponieważ ich punkty końcowe NIE znajdują się na granicy, wokół każdego jest trochę miejsca. Tak więc każdą z tych krawędzi można nieco „wyciągnąć”, rozszerzając obszar wielokąta i zaprzeczając jego maksymalności.

Uwaga 3 : Istnieją dwa przeciwległe po przekątnej wierzchołki prostokąta o maksymalnej powierzchni, które leżą na granicy wielokąta. (Wiemy z uwagi nr 2, że są co najmniej dwa, ale niekoniecznie, że są one naprzeciw siebie). Ale znowu przez sprzeczność, jeśli tylko dwa granice wierzchołków były sąsiadujące, to przeciwna krawędź (z których wierzchołków nie ma znajdują się na granicy) może zostać nieco wytłoczony, zwiększając obszar prostokąta i zaprzeczając jego maksymalności.

Uwaga # 4 : (EDYTOWANE) Jeśli prostokąt o maksymalnej powierzchni nie jest kwadratem, wówczas trzy jego wierzchołki będą leżały na granicy wielokąta.

Aby to udowodnić, załóżmy, że tak nie jest, tzn. Że prostokąt o maksymalnym polu powierzchni nie jest kwadratem, ale tylko dwa z jego wierzchołków znajdują się na granicy wielokąta. Pokażę, jak zbudować większy prostokąt, zaprzeczając maksymalności.

Zadzwoń wierzchołki prostokąta A, B, C, i D. Bez utraty ogólności, załóż, że Bi Dsą dwa, które są na granicy wielokąta. Ponieważ Ai Cwewnątrz wielokąta jest wokół nich trochę poruszającego się pokoju (reprezentowanego przez koła dookoła Ai Cna zdjęciu poniżej). Teraz narysuj okrąg wokół prostokąta i przesuń punkty Ai Ctrochę wokół koła o tę samą ilość (aby A'i na C'zdjęciu poniżej), aby nowy prostokątA'BC'Djest bardziej kwadratowy niż oryginalny prostokąt. Ten proces tworzy nowy prostokąt, który również znajduje się w oryginalnym wielokącie i ma większy obszar. Jest to sprzeczność, więc dowód jest gotowy.

Aby uwierzyć w ten dowód, musisz się przekonać, że pole prostokąta wpisanego w okrąg zwiększa się, gdy staje się ono „bardziej kwadratowe” (tzn. Różnica między długościami krawędzi maleje). Potrzebny jest również wielokąt, aby był wypukły, aby wszystkie nowe linie były w nim. I prawdopodobnie są tam inne drobiazgi, które zostały zmiecione pod dywan, ale jestem całkiem pewien, że wszystkie się sprawdzą.

Zrobiłem bardzo szybki i ohydny szkic twojej zielonej nuty w pytaniu. Nie mogłem tego opublikować jako komentarza, więc musiałem napisać odpowiedź, nawet jeśli nie jest to jedna.
Uważam, że na poniższym obrazku mamy prostokąt o maksymalnej powierzchni (nie idealny, to tylko szkic wykonany w programie Paint, aby dać pomysł), i nie sądzę, abyś mógł znaleźć większy, który miałby wspólną stronę z granice czarnego plygonu ...
Mogę się jednak mylić, w takim razie przepraszam.

Większość innych algorytmów znajduje prostokąt prostokątny o maksymalnej powierzchni wpisany w wypukły wielokąt i ma złożoność O(log n). Nie sądzę, aby twoje przypuszczenie, że maksymalny obszar wielokąta jest wyrównany z jedną ze stron, jest poprawne, ponieważ wszystko, co musisz zrobić, to obrócić nczasy wielokąta , co powoduje złożoność O(n log n), aw moich krótkich badaniach nie mogłem znajdź coś, co mówi, że to takie proste.

Jednak artykuł „ Największe zapisane prostokąty w wypukłych wielokątach” Knauer i in. al., opisuje algorytm aproksymacyjny, który zbliży cię do właściwej odpowiedzi.

Jak najlepiej rozumiem algorytm, opiera się on na jednym ze znanych wielokątów o maksymalnym obszarze, wyrównanych do osi, a następnie losowo próbkuje punkty w przestrzeni wielonośnej, generuje wiele osi z tych losowych próbek, iteruje nad tymi osiami i stosuje oś wyrównał algorytm do każdego z nich, a następnie zwraca największy prostokąt w tym zestawie.