# Distance to a convex polyhedron: about different approaches

I know there are a lot of litterature out there about convex polyhedra and distance computation, but I don't quite catch which one has the best computational complexity in practice and in theory. I also have an approach in mind that I would like to compare with those methods.

The space is $\mathbb R^3$. Suppose we have a query point $q$, and a convex polyhedron $P$ with $n$ vertices, $m$ edges and $f$ facets. We know that $n + f = m + 2$, and that $3n \leqslant 2m$ and $3f \leqslant 2m$. Suppose that for each facet we are also given the equation $e_i : a_ix+b_iy+c_iz+d_i=0$ defining its plane (let's assume that $P$ lie on its positive side).

The “naive” approach would be as follows:

1. Test if $q \in P$ in time $\mathcal O(f)$
2. For all facet $p_i$ such that $e_i(q) < 0$, project $q$ on $p_i$, and check if the result is strictly inside $p_i$. There can only be one such facet, and the projected point would have to minimize the distance from $P$. Since for every facet we iterate through all its edges, and that each edge belong to exactly 2 facets, the whole loop takes $\mathcal O(m)$ time
3. If not, then iterate through all the edges $uv$ and compute $\min(dist(q, uv))$. Complexity is again $\mathcal O(m)$

As $m=\mathcal O(n+f) = \mathcal O(n)$, the whole process would have linear time complexity.

Possible speed-up? Instead of checking the projected point for each facet whose $e_i(q)$ is $< 0$, I wondered if it is possible to, say, get the vertex of $P$ which is closest to $q$ (there may be ties), and look only at its adjacent facets? Alternatively can we use the information given by the plane equations (i.e. which region of the space $q$ belongs to) to prune out some facets from further check (i.e. we don't need to compute the projected point)? For example, if I look at and edge $uv$, and I know the value of $e_{i_1}(q)$ and $e_{i_2}(q)$ for the 2 facets on each side of $uv$, can I use it to decide which facet I should go and explore next?

Existing algorithms. Well, we have mostly two families of existings methods, but they tackle more general problems and I don't know if they could use the extra information that we have here.

• Gilbert–Johnson–Keerthi algorithm. Documented on Wikipedia which also links to some publicly-available (old?) code. Apparently it is mostly linear, but here we have only 1 point to 1 polyhedron, not 2 polyhedra.

• Quadratic programming. Also documented on Wikipedia, this seems to be the method used in CGAL (see the paper referenced at the end). Here it is also advertised as almost linear, but this also works for higher dimensions, and I'm afraid this might be using a sledgehammer to kill a fly.

So, the question is: how do theses methods compare with the “naive” approach I described, in terms of hidden constant in the $\mathcal O$?

Possible extensions.

1. How could we speed-up the distance query if we had a set of points $q_i$ to enquire about? (Not another polyhedron $Q$, just a set of points.)
2. If instead we just want to know a point in the set is at distance less than $d$ from the polyhedron, can we use other tricks? (Well, I guess has something to do with the Minkowski Sum of $P$, but even in GJK I don't think we compute the Sum exactly…)
-