7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How are the data of the convex polygon originally given? As inequalities? $\endgroup$ – user180040 Oct 4 '14 at 14:39
  • 1
    $\begingroup$ $P$ is defined by its set of vertices, counterclockwise. $\endgroup$ – peter Oct 4 '14 at 14:42
  • 1
    $\begingroup$ I think your proposed algorithm is incorrect. For example, say the vertices are $(100,0)$, $(-90,0)$ and $(0,-1)$, and $q$ is $(0,1)$. Then the closest point isn't on the edge between the two closest vertices, and it isn't the closest vertex either. $\endgroup$ – user180040 Oct 4 '14 at 14:55
  • $\begingroup$ Oh... yes you are right. So we should rather compute the distances between $q$ and each edges, intead of vertices? $\endgroup$ – peter Oct 4 '14 at 15:14
  • $\begingroup$ Well, that would work, except that I'm not sure about optimality. $\endgroup$ – user180040 Oct 4 '14 at 15:15
2
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

This is a special case of computing the distance between two convex sets (a point by itself is a convex set). This paper A fast procedure for computing the distance between complex objects in three-dimensional space was brought to my attention by Joseph O'Rourke and it references an $\mathcal{O}(\log M)$ algorithm for the two dimensional case. Here $M$ is the sum of vertices of both polygons, so in our case $M=n+1$. However they note that

Because of their complexity and special emphasis on asymptotic performance, it is not clear that the algorithms in the preceding papers are efficient for practical problems where $M$ is large, but not exceedingly large. Unfortunately, very few, if any, computational experiments have been done.

The algorithm they present has however gained a lot of practical use - for example it is used in many physics engines (such as bullet physics) since the game objects are approximated by convex shapes.

The proper linear brute force algorithm is to compute the distance between $q$ and all vertices, compute the shortest distance between $q$ and all line segments (faces) and then pick the minimum. However this makes no use of the convexity.

EDIT: One way to make the brute force algorithm more efficient is probably to use some data structure like a k-d tree for nearest neighbor search but that is just an idea and i haven't worked out the details.

$\endgroup$
1
$\begingroup$

You could do something that is somewhat like binary search indeed: To find the closest point on $P_1P_2P_3\ldots P_n$, find the closest point on $P_1P_3P_5\ldots P_{\lceil n/2\rceil}$. If it is between $P_k$ and $P_{k+2}$ then we need only test vertex $P_{k+1}$ and its adjacent edges for the original polygon. If it is exactly at $P_k$, we also need only check a few neighbouring cases.

$\endgroup$
1
$\begingroup$

If the convex polygon is represented by the intersection of finitely many half-planes

$$P := \{ x \in \mathbb R^2 \mid A x \leq b \}$$

then we can find the point $x^* \in P$ closest to a given $y \in \mathbb R^2$ by solving the quadratic program

$$\begin{array}{ll} \text{minimize} & \|x - y\|_2^2\\ \text{subject to} & A x \leq b \end{array}$$

If the minimum is zero, then $y \in P$. Hence, we can use QP to decide whether $y \in P$ or $y \notin P$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.