Find a point on the convex hull of a given set of points which is closest to a given point.

Question

I have an unanswered question on Stack Overflow that might more related to mathematics than programming. So the part where I am having a problem is described below.

EDIT: I reformulated the whole problem hoping that will be clearer.

Let $\mathcal{A}$ be a set of $m$ points: $$ \mathcal{A} = \{P_i \in \mathbb{R}^6, i \in [1,\ldots, m]\}. $$

From this set of points, a convex hull $\mathcal{C}$ (the smallest convex set that contains the points ${P_i}$) can be defined such that: $$ \mathcal{A} \subseteq \mathcal{C} $$

Let's define $Q \in \mathbb{R}^6$ such that: $$ Q \not\in \mathcal{C} $$

How do I find $Q^{\prime} \in \mathbb{R}^6$, the closest point from $Q$ belonging to the convex hull $\mathcal{C}$: $$ Q^{\prime} \in \mathcal{C}, \forall r \in \mathcal{C}\quad ||Q^{\prime}-Q|| \leq ||r-Q|| $$

I am looking for any algorithm or mathematic method to solve such problem so that I can implement it in my code.

For information: I am using the python scipy implementation of the qhull library for finding the convex hull from $\mathcal{A}$.

Answer 1

Why not just this ...

(1) Using this Qhull libary function

$\qquad$http://www.qhull.org/html/qh-faq.htm#closest

find the facet of the convex hull which is closest to the given point.

(2) For that facet ($k$-dimensional with $0 \le k \le n-1$), find the equations of the $k$-plane containing it.

(3) Using standard techniques from Vector Calculus, find the point on that $k$-plane which is closest to the given point.

Done.

If you post an actual numerical example, we can see if this works.

Answer 2

I will post some piece of information I got from google and co which might be quite close to what I am looking for.

A similar question here seems to suggest that this is simply a quadratic programming problem formulated as such: $$ \begin{align} \text{minimize} & \quad ||Q^{\prime}Q||\\ \text{subject to} & \quad A Q^{\prime} + b = 0\\ \text{subject to} & \quad \mathbf{G} Q^{\prime} + h \leq 0. \end{align} $$ $A Q^{\prime}+b = 0$ specifies that the point $Q^{\prime}$ is on the closest hull boundaries and $\mathbf{G} Q^{\prime} + h \leq 0$ specifies that $Q^{\prime}$ is inside or on the other boundaries.

If we develop $||QQ^{\prime}||$, the problem is written as (correct me if I made a mistake): $$ \begin{align} \text{minimize} & \quad 2\left(\frac{1}{2} {Q^{\prime}}^{T} \mathbf{I} Q^{\prime} - Q^T Q^{\prime}\right)\\ \text{subject to} & \quad A Q^{\prime} + b = 0\\ \text{subject to} & \quad \mathbf{G} Q^{\prime} + h \leq 0, \end{align} $$ with $\mathbf{I}$ the identity matrix.

If we didn't have the second constraint, the resolution of a linear solution should yield to the solution as explained on Wikipedia quadratic programming page, but this cannot be used.

According to qhull documentation:

The convex hull of a point set P is the smallest convex set that contains P. If P is finite, the convex hull defines a matrix A and a vector b such that for all x in P, Ax+b <= [0,...].

Qhull computes the convex hull in 2-d, 3-d, 4-d, and higher dimensions. Qhull represents a convex hull as a list of facets. Each facet has a set of vertices, a set of neighboring facets, and a halfspace. A halfspace is defined by a unit normal and an offset (i.e., a row of A and an element of b).

I am not entirely sure at this point but the closest hyperplane equation should lead to the vector $A$ and float $b$, and all the other hyperplanes give the matrix $\mathbf{G}$ and vector $h$. I don't think an analytical solution exists (correct me if I am wrong) so the problem must be solved with a non-linear optimiser such as SLSQP for each facet of the convex. The solution point $Q^{\prime}$ will be the closest point to $Q$.