Sa luam un exemplu:
!notiuni-de-geometrie-si-aplicatii?polig1!

In imaginea de mai sus punctele $P{~1~}$,..{$P{~6~}$} reprezinta varfurile poligonului iar punctele $P{~7~}$, $P{~8~}$, $P{~9~}$ reprezinta interogarile. Cu rosu sunt trasate diagonalele care delimiteaza sectoarele, si le vom tine ca drepte, sortate dupa panta, impreuna cu dreptele suport pentru cele 2 laturi care au un capat in punctul $P{~1~}$. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul $P{~8~}$ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor $P{~4~}$ si $P{~5~}$. Astfel vom verifica daca punctul $P{~8~}$ se afla in interiorul triunghiului determinat de punctele $P{~1~}$, $P{~4~}$, $P{~5~}$. Vom proceda asemanator si pentru celelalte interogari cu mentiunea ca trebuie sa avem grija la cazurile in care punctul nu se afla in nici unul din sectoare, insa asta se poate face usor cu o verificare inainte de a porni cautarea binara.

In imaginea de mai sus punctele $P{~1~}$,..{$P{~6~}$} reprezinta varfurile poligonului iar punctele $P{~7~}$, $P{~8~}$, $P{~9~}$ reprezinta interogarile. Cu rosu sunt trasate diagonalele care delimiteaza sectoarele, si le vom tine ca drepte, sortate dupa panta, impreuna cu dreptele suport pentru cele 2 laturi care au un capat in punctul $P{~1~}$. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul $P{~8~}$ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor $P{~4~}$ si $P{~5~}$. Astfel vom verifica daca punctul $P{~8~}$ se afla in interiorul triunghiului determinat de punctele $P{~1~}$, $P{~4~}$, $P{~5~}$. Vom proceda asemanator si pentru celelalte interogari cu mentiunea ca trebuie sa avem grija la cazurile in care punctul nu se afla in nici unul din sectoare (P{~9~}), insa asta se poate face usor cu o verificare inainte de a porni cautarea binara.

Aceasta solutie are complexitate O(NlogN + MlogN).