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

21

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.

wprowadź opis zdjęcia tutaj

Deweloper
źródło
1
Czy możesz określić, z jakiego oprogramowania korzystasz? Opublikuj swoją pracę do tej pory lub ogólne podejście wypracowane w celu rozwiązania tego problemu. Może ktoś może poprawić to, co już zrobiłeś. Z mojego doświadczenia wynika, że ​​przyniesie to o wiele bardziej przydatne odpowiedzi niż zwykłe opublikowanie pytania „nieoczekiwanie”.
Martin
1
Ściśle związane: gis.stackexchange.com/questions/22895/... .
whuber
Oprogramowanie @Martin: Programowanie Pythonzostanie włączone, Fortranjeśli będzie wymagane. Mamy przypuszczenie, że na podstawie naszego poprzedniego postu, o którym również wspomniałem powyżej whuber, może to być prostokąt z krawędzią wspólną z wielokątem.
Deweloper
1
Twój problem jest naprawdę interesujący i myślę, że udało mi się znaleźć tu i tutaj algorytm rozwiązywania problemów .
nickves
1
@nickves Dzięki za linki. Czy mógłbyś podać te informacje jako odpowiedź z małym wyjaśnieniem algorytmów? Potencjalnie dobra odpowiedź zostanie zaakceptowana.
Deweloper

Odpowiedzi:

4

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.

Konstruowanie nowego prostokąta

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ą.

csd
źródło
Uwaga # 4 jest podejrzana, ponieważ „poruszanie się” dwóch pozostałych wierzchołków spowoduje utworzenie prostokątów.
whuber
Prawdziwe. Jednak wizualizacja czwartego przykładu nie jest całkiem poprawna (jeśli 2 wierzchołki znajdują się na granicy wielokąta, nie można go dalej rozciągać). Nie mogę jednak dokładnie wyjaśnić, jak to wyjaśnić (próbowałem napisać komentarz, ale zrobiłem się zbyt bałaganiarski), ale ufam, że masz rację.
Saryk
Myślę, że istnieją kontrprzykłady do odnotowania # 4. Te, które znalazłem, wymagają jednak pewnych obliczeń; najprostszym jest zaburzenie nieregularnego sześciokąta (kwadratu z dwoma przeciwległymi narożnikami lekko obciętymi).
whuber
Zgodził się, że uwaga nr 4 jest podejrzana. Dziś wieczorem przyjrzę się bliżej i naprawię to lub usunę.
csd
+1 To niezła rozdzielczość trudności. Dzięki za edycję!
whuber
3

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.
Szybki szkic zrobiłem na Paint

Saryk
źródło
3
Dobry punkt (+1). Istnieje jednak znacznie prostszy przykład: rozważ problem wpisania prostokąta o maksymalnym polu powierzchni w regularnym ośmiokącie. Łatwo jest zobaczyć (i łatwo udowodnić, najpierw znajdując maksymalny kwadrat w obwodzie ośmiokąta), że rogi rozwiązania pokrywają się z naprzemiennymi wierzchołkami ośmiokąta i że to rozwiązanie jest znacznie większe niż jakikolwiek prostokąt wpisany w krawędź.
whuber
Właściwie (mam teraz duże wątpliwości), zewnętrzny najmniejszy prostokąt (te z tego postu ) tego wielokąta nie ma takiej samej orientacji jak jedna ze stron, prawda? (
Widziałbym
3
Nawiasem mówiąc, ten wielokąt nie jest wypukły. Pierwotne pytanie ogranicza się do wypukłych wielokątów.
csd
2
@csd To świetna uwaga, ale Saryk nadal ma rację, jak pokazuje mój kontrprzykład. Saryk, nie ma problemu z minimalnym prostokątem ograniczającym obszar: łatwo jest (rygorystycznie) udowodnić, że musi zawierać bok wypukłego kadłuba. Uważam, że maksymalny prostokąt wpisany w pole powierzchni (wypukłego wielokąta) musi mieć tylko dwa wierzchołki dotykające granicy, nigdy więcej.
whuber
2

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.

leder
źródło
Czy w pierwszym zdaniu jest literówka? Nie może istnieć algorytm O (log (n)), ponieważ sam odczyt współrzędnych jest operacją O (n)!
whuber
Link jest martwy
niebezpiecznedave
1
@dangerousdave - Znaleziono alternatywny link na jak długo to trwa ....
lreeder