Is binary-search really required in Chan's convex hull algorithm?
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.