[Math] algorthm to find a farthest point in a convex polygon to an external point

algorithmsconvex-analysisgeometry

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:

  • If the vertices are sorted by angle (azimuth) from any interior point (e.g. the centeroid), you can achieve $O(\log n)$.
  • If the vertices are in any order, in the worst case you will need $\Omega(n)$ checks.

I hope this helps $\ddot\smile$

Related Question