I have a little doubt about Chan's algorithm.
From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the second phase is to compute $m$ points $\{p_1 ... p_K\}$. On $i$-th iteration the candidate $p_i$ is chosen among $\{q_1 ... q_K\}$, where $q_j \in \mathcal{CH}(Q_j)$ is a point such that every other point of $\mathcal{CH}(Q_i)$ lies to the left of line $p_{i - 1}q_j$.
According to the Wikipedia page, each point $\{q_1 ... q_K\}$ of set is searched in $\mathcal{O}(\log m)$ using binary search, which is the main reason that whole second phase takes $\mathcal{O}(Kh + Kh \log m)$, where $h$ is the size of resulting convex hull (which is unknown at the beginning).
I doubt that it is necessary to perform this binary search for every candidate-point $q_i$ on each iteration. I get that, when we just start with $p_0$, there's no other way to do this. What about the following iterations? As I think of it, on each iteration the point $q_i$ either stays the same or it changes to one of the successive point of $Q_i$ in ccw-order. And one point cannot become a candidate more than twice (or even once?). If that is the case, why can't we use $K$-pointer technique and just set $q_i \leftarrow q_{i + 1}$ while $q_i$ is not a tangent line for current iteration. There shouldn't be more than $2m$ candidate changes for each $Q_i$ for all $m$ iterations. Wouldn't the resulting complexity $\mathcal{O}(Kh + Km)$ be better than $\mathcal{O}(Kh + Kh\log m)$?
And some pictures that aren't on wiki page to give a better idea of this second phase.
The first one shows what are the candidates.
And the second one should provide an intuition about choosing $q_i$ for the next iterations.
