Rys. 1 Wielokąt  można umieścić wewnątrz wielokąta

Rys. 2 Wierzchołek  jest wierzchołkiem krytycznym dla boku

Niech  będzie wielokątem o wierzchołkach  który chcemy umieścić wewnątrz wielokąta  o wierzchołkach (przyjmujemy, że  i  ). Niech  będzie dowolnym punktem wewnątrz wielokąta (Rys. 1). Załóżmy dla uproszczenia, że żadna para boków wielokątów nie jest równoległa oraz żaden bok nie jest pionowy.

Przez (dla ) oznaczmy tę półpłaszczyznę wyznaczoną przez prostą  która zawiera wielokąt  Przesuńmy teraz wielokąt  tak, aby zawierał się w   i aby odległość punktu  od prostej  była jak najmniejsza; oznaczmy tę odległość przez  Zauważmy, że  możemy obliczyć bez kłopotu, jeśli wyznaczymy wierzchołek przesuniętego wielokąta  który leży na brzegu półpłaszczyzny  nazwiemy ten wierzchołek krytycznym dla boku (Rys. 2).

Zauważmy, że wielokąt  zawiera się w   dokładnie wtedy, gdy punkt  zawiera się w półpłaszczyźnie  która jest wyznaczona przez prostą równoległą do  w odległości  Jest jasne, że  znajduje się wewnątrz  dokładnie wtedy, gdy znajduje się w każdej z półpłaszczyzn  innymi słowy wtedy, gdy punkt  należy do przecięcia półpłaszczyzn  Co więcej, przecięcie półpłaszczyzn zawiera wszystkie możliwe położenia punktu

Do pełnego rozwiązania pozostaje zatem pokazanie, jak efektywnie wyznaczyć wierzchołki krytyczne, a następnie przecięcie półpłaszczyzn.

---

Wyznaczanie wierzchołków krytycznych

Rys. 3 Nachylenia boków wielokątów naniesione na okrąg.

Narysujmy okrąg i zaznaczmy na nim, dla  punkt styczności  prostej stycznej do okręgu i równoległej do prostej  Analogicznie zaznaczamy punkt  dla prostej (Rys. 3). Zauważmy, że wierzchołek  jest krytyczny dla boku  jeśli na okręgu punkt  leży pomiędzy punktami  oraz  Wystarczy zatem wyznaczyć kolejność punktów na okręgu – to można zrobić w czasie  gdyż należy scalić dwa posortowane ciągi punktów (zakładamy przy tym, że znamy kolejność wierzchołków na obwodach wielokątów).

Na ten problem można spojrzeć też inaczej. Wyobraźmy sobie dwie proste równoległe, które jednocześnie obracają się wokół wielokątów, będąc do nich stycznymi. Ilekroć prosta styczna do  zawiera pewien jego bok, to prosta styczna do  przechodzi przez wierzchołek krytyczny dla tego boku.

Pozostawiamy Czytelnikowi zaimplementowanie tego pomysłu, tak by działał w czasie  Metoda prostych równoległych pozwala rozwiązać wiele problemów dotyczących wielokątów wypukłych – zainteresowani Czytelnicy więcej szczegółów mogą znaleźć w Internecie pod hasłem rotating calipers.

---

Wyznaczanie przecięcia półpłaszczyzn

W ogólności problem ten dla  półpłaszczyzn wymaga czasu  ale my znowu skorzystamy z tego, że znamy kolejność wierzchołków w wielokącie  zatem nasze półpłaszczyzny  są posortowane według współczynników kierunkowych ich brzegów (prostych ), co pozwala nam rozwiązać ten problem w czasie

Rys. 4 Rozpatrujemy prostą  na stosie znajdują się proste  Punkt  znajduje się na prawo od punktu  zatem usuwamy ze stosu prostą  Punkt  jest na lewo od  zatem na stosie pozostaną proste

Najpierw pokażemy, jak wyznaczyć „dolne” przecięcie, tzn. dla półpłaszczyzn, które mogą stanowić dolny brzeg wielokąta będącego przecięciem. Przeglądamy półpłaszczyzny w kolejności rosnących współczynników kierunkowych prostych  Będziemy utrzymywać następujący niezmiennik: po rozpatrzeniu prostej  na stosie znajdują się te proste z ciągu  które mają nietrywialne przecięcie z brzegiem zbioru

Rozpatrując  robimy co następuje: dopóki punkt przecięcia prostych  i  (przedostatniej i ostatniej prostej na stosie) znajduje się na prawo od punktu przecięcia prostych  i   usuwamy ostatnią prostą ze stosu. Na końcu dodajemy prostą  na stos (patrz Rys. 4).

Analogicznie wyznaczamy przecięcie „górnych” półpłaszczyzn. Obliczenie przecięcia powstałych zbiorów w czasie  pozostawimy jako ćwiczenie dla Czytelnika.