Finding a point in a convex polygon farthest to an external point

Question

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)$.

Answer 1

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$

Answer 2

I'm thinking here in terms of a strategy where you spend time analyzing the polygon, then run many queries on many points $q$, so you want to optimize the time per $q$. It would be different if you were given many polygons and only wanted to test one point per polygon.

Let $R_{a,b}$ be the half-plane where point $a$ is farther than point $b$. Then $\bigcap_{i \neq a} R_{a,i}$ is the convex region where point a is farther than all other points.

So you can calculate a partition of the plane into $n$ convex regions. Then your problem becomes finding which convex region the query point $q$ falls within, and that can be done with a binary tree in $O(\log n)$ time.

Answer 3

A general algorithm which is faster than O(n) is not possible. To see why, consider a regular polygon of any number of vertices, and a query point $q$ at its center. Each vertex of this polygon is now equally far from $q$, and these are the farthest points. We can now take any vertex $v_i$ and move it slightly away from $q$, such that the farthest point is now strictly this vertex, and we can do this without breaking convexity. All other vertices remain the same.

The fact that this is possible means that it's always necessary to check all vertices. It's not possible with this polygon to take a subset of the vertices, perform some test on this subset, and based on the outcome of that test conclude that a larger range which includes vertices not in this subset can't contain the farthest point. For example, if the subset does not include vertices $v_i$ and $v_j$, then we can never use this subset to distinguish between cases where $v_i$ vs $v_j$ was moved.

The same idea also works when $q$ has to be external to the convex polygon. Simply take the half of the regular polygon formed by the vertices strictly above a horizontal line through $q$.