[Math] Tangent lines to polygon on logarithmic time.

Question

I've been reading T.M. Chan algorithm for convex hull of a 2D polygon, here he says that we can find a support line (tangent line) to a polygon given that this polygon is convex and we have its vertices on CCW order in $O(\log H)$ time with $H$ being the number of vertices on the convex hull of the polygon.

Now, I could take this for granted but I decided to see exactly how, since we had it in class but with time $O(n)$. By looking at the references (Shamos and Preparata book) and a Chazelle article I find myself more confused than happy.

Looked into some other notes about convex hull where Chan's algorithm is simplified into text (which is great because now I can understand the time bound better) but here the part about $O(\log H)$ for tangent lines is took by granted and actually left as an exercise so I decided to try it.

To find lets say just a right tangent line to a polygon $P$ given its vertices $p_0,p_1,\dots,p_n$ in CCW order and a point $q$ that lies outside the boundary of $P$, I think first I need to locate the maximum and minium $y-$oriented points, I can do this in $O(\log n)$ ($n$ points on $CH(P)$), but then I'm stuck in the part where I need to do binary search over the other points of $CH(P)$ to find the tangent line.

Any hints?

Right tangent line from a query point $q$ located outside $P$: find a vertex $p_i$ such that $P$ is contained in the closed half-plane to the left of the oriented line $qp_i$.

Answer 1

To be read in order, and ideally not all at once.

Hint 1

Given a vertex $p_i$, let $\mathbf n_i$ the unit vector such that the closed half-plane "to the left" of oriented line $qp_i$ is: $$\{ x\in\mathbb R^2\mid \langle x-p_i,\,\mathbf n_i\rangle \ge 0\}$$ where $\langle \mathbf a,\,\mathbf b\rangle$ denotes the scalar product of vectors $\mathbf a$ and $\mathbf b$. Looking at those unit vectors should be useful.

Hint 2

Vertex $p_i$ supports a right tangent line if and only if $\langle p_{i-1}-p_i,\, \mathbf n_i\rangle \ge 0$ and $\langle p_{i+1}-p_i,\,\mathbf n_i\rangle\ge 0$, with $p_{-1}=p_n$ and $p_{n+1}=p_0$.

Hint 3

If a vertex $p_i$ doesn't satisfy the two conditions from hint 2, you can (very often) figure out "which way" the proper vertex is wrt $p_i$. The only situation where you cannot figure that out, is if $p_i$ supports a "left tangent line".

Hint 4

Dichotomic search?

Hint 5

No.