We are given a convex polygon $C = \{P_1, P_2, \dots, P_n\}$, where the points are ordered either clockwise or counter-clockwise. Additionally, we have a point $P_\text{new} = (x, y)$ that lies outside the convex hull. The goal is to find the point $P_i$ in $C$ that is closest to $P_\text{new}$ in a _logarithmic_ time complexity. ($O(\log n)$.) ![Convex polygon and a point](https://preview.redd.it/closest-point-on-a-convex-hull-in-log-n-v0-qrvz5rfp783e1.png?width=412&format=png&auto=webp&s=317abae8f9270e9b3853f7b4b29fffbd800cff2c) We can't use sorting because that would take $O(n \log(n))$ time, and also we can't use binary search because of the shape of a convex hull and we might delete the half that contains the answer.