Given a point q, direction w and point set P with convex hull (v_1, …, v_n) known, give an algorithm to find the point in P that (q, w) touches first when rotated counterclockwise in O(log(n)) time. REMARK: We can assume that (v_1, …, v_n) is sorted counterclockwise.

Step 1
To check the orientation of $v_i-<!--\; -\; -->q$ vs. w, we can use the cross product (after viewing our ${\mathbb{R}}^2$ as subspace of ${\mathbb{R}}^3$). This amounts to checking the sign of the expression
$F(i):=(v_{i,y}-<!--\; -\; -->q_y)w_x-<!--\; -\; -->(v_{i,x}-<!--\; -\; -->q_x)w_y=(v_i-<!--\; -\; -->q)\cdot <!--\; \cdot \; -->w^{\perp <!--\; \perp \; -->}$ where $w^{\perp <!--\; \perp \; -->}=(-<!--\; -\; -->w_y,w_x)$ is w rotated left by 90°.
All $v_i$ for which F(i) is positive are on the same side ("ahead") of the line given by point q and direction w, all $v_i$ with negative sign are on the other side ("behind"), and all with result 0 are on the line itself.
Step 2
If q is inside the convex hull of P, we are looking for a change from negative to positive (or zero) sign along the cyclically ordered vertex sequence. Binary search is fine as soon as we have obtained one i with $F(i)<0$ and one j with $F(j)\ge <!--\; \ge \; -->0$. Picking a random index will give us one of the signs, but it is not that trivial to find an index with the other sign. To do so, we may want to look for a maximizer or minimizer of $F(v_i)$. We may use that F switches between increasing and decreasing only once. So start with $i=1$, $j\approx <!--\; \approx \; -->\frac{1}{2}n$, $k\approx <!--\; \approx \; -->\frac{2}{3}n$. If differnet signs occur at these, we are already done (up to the final binary search). So assume that F(i), F(j), F(k) are all negative and we want to look for a maximizer (or similarly: all positive and minimizer). By perhaps using cyclic rearrangement of i, j, k, we may assume that $F(i)<F(j)>F(k)$, i.e., the maximum among these three values is at the middle index. To facilitate distance calculations, I shall however assume that$i<j<k$. Now we know that the maximizer is between i and k. We can pick $l\ne <!--\; \ne \; -->j$ between i and k and thereby reduce our interval of length $k-<!--\; -\; -->i$ to an interval of length at most $max\{k-<!--\; -\; -->l,j-<!--\; -\; -->i\}$ if $l<j$ or $max\{k-<!--\; -\; -->j,l-<!--\; -\; -->i\}$ if $l>j$ by picking those three consecutive out of four indices that have the maximum in the middle again. The essential trick is to pick l smartly so that the interval length decreases fast enough. Picking l such that it split [i,k] roughly by the Golden Ratio ensures this.