Determine whether a point lies in a convex hull of points in O(logn)

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one myself. Let a[] be an array containing the vertices of the convex hull, can I preprocess this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(log n) time?

This is a classic problem in computational geometry, called Polygon Inclusion Problem. Further, you are considering its special case --- Convex Inclusion.

In chapter 4 of this thesis by Michael lail Shamos 1978, you will find that:

Generally,


Theorem 4.2 (Page 92): Whether a point is interior to a simple $n$-gon can be determined in $O(n)$ time, without preprocessing.

and for convex polygon,


Theorem 4.3 (Page 95): The Inclusion question for a convex $n$-gon can be answered in
$O(\log n)$ time and $O(n)$ space, given $O(n)$ preprocessing time.

The proofs of these two theorems contain the algorithms you are looking for.

StackExchange Computer Science Q#39970, answer score: 7