Единственное решение этой проблемы, о котором я знаю, требует O(n) полигона предварительной обработки времени. После этого каждая точка запроса для предварительно обработанного многоугольника обрабатывается за O(lg n) времени.
Просто возьмите точку P внутри многоугольника (назовем это «полюсом») и для каждой вершины нарисуйте луч, выходящий из P и проходящий через вершину. Считайте, что это полярная система координат с началом в P, причем вся полярная плоскость разделена на сектора этими лучами. Теперь, учитывая вашу точку запроса, вам просто нужно преобразовать ее в полярные координаты с началом координат на нашем полюсе P. Затем просто выполните бинарный поиск, чтобы определить конкретный сектор, содержащий точку запроса. Заключительная внутренняя / внешняя проверка внутри сектора (проверка точки и края) является тривиальной операцией O(1). Каждый запрос обрабатывается за O(lg n) время, необходимое для двоичного поиска.
Этот подход будет работать с большим классом полигонов, чем просто выпуклыми. Он охватывает класс так называемых звездных многоугольников, то есть многоугольников, у которых есть точка, из которой вся внутренность многоугольника может быть "видна" или "наблюдаема".
Время предварительной обработки O(n) обусловлено необходимостью заранее определить местоположение полюса.
P.S. Я увлекся размышлениями о более общем случае. Если ваш многоугольник выпуклый, вы можете просто использовать любую из его вершин в качестве полюса. Таким образом, вы сразу получаете алгоритм O(lg n), предварительная обработка не требуется.