Estoy tratando de resolver algunos ejercicios del libro "Algoritmo y aplicaciones de la geometría computacional, 3rd - de berg et al" del capítulo 6 - Ubicación de puntos. Desafortunadamente, no tengo idea de cómo resolver el siguiente ejercicio:

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.

Mi idea hasta ahora: La única forma que sé para determinar si un punto se encuentra dentro de p en O (log n) es usar un gráfico acíclico dirigido. Para usar un gráfico acíclico dirigido necesito construirlo, lo cual es imposible en O (log n). Entonces, de alguna manera necesito usar la matriz ordenada, pero la única solución que conozco con una matriz costará O (N).

Espero que alguien pueda ayudarme.