Given a point $q$ external to a convex polygon $P$, propose an algorithm to compute a farthest point in $P$ to $q$.
One can always have at least one vertex of $P$ in the set of farthest points of $P$ to $q$. So a linear algorithm is possible, computing for each vertex its distance to $q$.
I wonder if a faster algorithm is possible. Initially I thought so, but I am now more enclined to try and prove that such algorithm is $\Omega (n)$.
Best Answer
Hint:
I hope this helps $\ddot\smile$