Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$?
A linear algorithm of course works, computing the distance for each vertex of $P$, finding the 2 closest vertices $u$ and $v$ to $q$ and then projecting $q$ onto the edge $uv$, if such projection belongs the edge. If not, returning the closest vertex works.
But I was wondering if a binary search could not be also possible, using the convexity. The running time would be $\mathcal{O}(\log n)$.
Best Answer
Create a Voronoi diagram then, using edges of the Voronoi regions, create a binary decision tree with depth $O(\ln n)$ to determine the region in which each query point lies.
You can do better if you are willing to spend memory. Find a boundary circle where all the regions outside of it are radial, i.e. they look like a WWII Japanese flag and any ray from the origin intersects at most 2 of them. For query points within the circle, subdivide the area into a grid of squeares, each small enough so that only $O(1)$ work is required to determine which region the point lies within. For points outside the circle, similarly subdivide the angles into small enough radial regions such that each region intersects with only 2 Voronoi regions.
Then the algorithm becomes this:
angle = atan2(q.y, q.x)
, thenradial_region_idx = (pi + angle) * num_radial_regions / (2 pi)
x_idx = floor(q.x / dx)
andy_idx = floor(q.y / dy)
.(x_idx,y_idx)
, perform $O(1)$ work, and we know which region we're in. End.