Is binary-search really required in Chan's convex hull algorithm?

Question

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 2ドルm$ 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. enter image description here

And the second one should provide an intuition about choosing $q_i$ for the next iterations.

enter image description here

Answer 1

I think this is correct... see 2. Chan’s Algorithm p4, Remark.

Remark. Using a more clever search strategy instead of many binary searches one can handle the conquer phase in $O(n)$ time. However, this is irrelevant as far as the asymptotic runtime is concerned, given that already the divide step takes $O(n \log H)$ time.

Anyway, the complexity is bounded by the divide phase.