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. enter image description here

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

enter image description here


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.