[Math] Algorithm to find the point in a convex polygon closest to an external point

algorithmscomputational geometryconvex optimizationconvex-analysisgeometry

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:

  1. Is $q$ within the circle? If so, goto 4.
  2. Calculate angle = atan2(q.y, q.x), then radial_region_idx = (pi + angle) * num_radial_regions / (2 pi)
  3. Use radial_region_idx to look up the answer or the boundary between the two voronoi regions. After $O(1)$ work we know which Voronoi region we're in. End.
  4. Calculate x_idx = floor(q.x / dx) and y_idx = floor(q.y / dy).
  5. Look up the record for tile (x_idx,y_idx), perform $O(1)$ work, and we know which region we're in. End.
Related Question