Estou tentando resolver alguns exercícios do livro "Algoritmo e aplicações de geometria computacional, 3rd - de berg et al" do capítulo 6 - Localização dos pontos. Infelizmente, não tenho ideia de como resolver o seguinte exercício:

Given a convex polygon P as an array of its n vertices in sorted order
along the boundary. Show that, given a query point q, it can be tested in
time O(log n) whether q lies inside P.

Minha idéia até agora: A única maneira que sei determinar se um ponto está dentro de p em O (log n) é usar um gráfico acíclico direcionado. Para usar um gráfico acíclico direcionado, preciso construí-lo, o que é impossível em O (log n). Então, de alguma forma, preciso usar a matriz ordenada, mas a única solução que conheço com uma matriz custará O (N).

Espero que alguém possa me ajudar.