Closest point on a convex hull in log(n)

Question

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

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.

Answer 1

Start of an answer:
Given $P_{new}$ outside

1. a regular $(2n+1)$gon (simple case):
   Pick an edge $e$ and its vertices $v_a$ and $v_b$.
   If their distances to $P_{new}$ are equal,
   either both are closest to $P_{new}$, or the vertex $v_{oe}$ opposite to $e$ is.
   Else the closest vertex is between $v_{oe}$ and the closer of $v_a$ and $v_b$, to be found using binary search.
2. part of a regular polygon:
   Start with a wedge-shaped third of a regular polygon with lots ( $n - 1$) of vertices on the outcircle and one incident to the centre. Now move "the tip vertex" $v_t$ a bit closer to the segment; $P_{new}$ is somewhere between $v_t$ and the centre. For good measure, move every third vertex slightly inward (such that it is just outside the chord through its neighbours).
   What makes this case look hard?
   Start at one of the vertices moved inward, say, $v_i$, the next counter-clockwise from the one opposite to $v_t$:
   both its neighbours will be farther from $P_{new}$. Worse, the ninth in both directions, while local minima of distance too, will be farther than $v_i$, too.

Answer 2

Let's at first find a polygon edge, closest to the external (relative to the polygon) query point q. Then, if we really need, we will be able to choose one of the edge ends.

The algorithm is based on external bisectors - rays, which originate at each polygon vertex and divide the angle (which is more than 180 grad) into two equal angles. These bisectors never intersect because of the convexity of the polygon. The guiding vector of such a bisector can be calculated as a half-sum of external normal vectors for two adjacent edges. The closest edge (which we are looking for) together with its two bisectors defines a part of plane, where the query point lies.

We will call such a part of plane a cut wedge - because its vertex was cut by the polygon boundary. In general, we can consider cut wedges, consisting of a polyline (part of the polygon boundary) and two bisectors at its ends. We will need to check if the query point lies inside such a cut edge, but fortunately we don't need to traverse the polyline to perform these checks for each edge - we already know that the query point is outside the polygon. So, we can verify that the query point lies inside the cut wedge checking only its two bisectors. If the point is inside, we construct a trial bisector in the middle of the polyline, and check one of "halves".

So, this a binary search, which starts with a pair of complementary cut wedges (for example, with bisectors, originating from $p_0$ and $p_{n/2}$) and ends when the cut wedge, containing the query point, shrinks to a single edge.