I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$. Given a new point $y$, how can I verify that distance from $y$ to the convex hull of $x_i$ is less than a given $\varepsilon$? It's not important for me whether the distance is Euclidean, any $p$-norm would work. I am interested in efficient ways to compute this.

As requested, some details:

  1. I start building this cluster from a single point, and add points to it as soon as they lie within $\varepsilon$ distance from its convex hull. Otherwise, I start a new cluster and close the first one. Usually clusters are of reasonably small size (about $10^2$ or $10^3$ points), and the total number of unclustered points is $10^5$ or more.
  2. The points distribution is naturally clustered, so there are decent gaps between the data points.
  3. The new point may belong both to interior and to exterior of the cluster.
  4. The distance evaluation does not really have to be precise, that's one of the reasons I've mentioned which $p$-norm to use does not really matter to me.

without more indication about constraints, a basic solution would be to precompute a decomposition of the convex hull into a tiling of simplexs, then to compute the distance to the convex hull that is the min of distances from $y$ to each simplex.

If $y$ can't be inside the convex hull, simplications are possible, like, consider only the distance to the hypersurface of the convex hull.

Many algorithms exist to buid such tiling with different efficiency depending on your case.

Many optimizations are possible when evalutating the distance, e.g., precalculating a Binary space partitioning .

  • $\begingroup$ Well, I can easily check whether $y$ is inside the hull, and only compute the distance otherwise. $\endgroup$ – Ulysses Nov 4 '15 at 7:33
  • $\begingroup$ how do you check easily, without having a cost that is very close to the complexity of the evaluation of distance ? $\endgroup$ – Fabrice NEYRET Nov 4 '15 at 8:41
  • $\begingroup$ I am not sure about the cost of the inclusion algorithms, but the method you suggest seems to be a bit more complex. Perhaps, I am wrong in that. $\endgroup$ – Ulysses Nov 4 '15 at 8:47
  • $\begingroup$ Once you know you are outside, the complexity collapse to distance to convex border. But if you don't know, it is the min distance to all the points of the volume. Computing distance to volume when you occurs to be inside and checking inclusion is basically the same thing ! (ok, optimizations might differs a bit, but I don't think it changes the compared complexity). $\endgroup$ – Fabrice NEYRET Nov 4 '15 at 8:54
  • $\begingroup$ But maybe you should tells us whether you are interested in computer-science optimizations (e.g. based on precalculation of partitionning using BSP or BVH or n-trees or kd-trees, etc ) or only in the "brute force maths". $\endgroup$ – Fabrice NEYRET Nov 4 '15 at 8:56

Taking the $\max$-norm, for example, the calculation of the distance is LP:

$$ \min\epsilon\qquad $$ \begin{align} &-\epsilon \mathbb{1}\le\sum_{i=1}^n\lambda_i x_i-y\le\epsilon\mathbb{1},\\ &\sum_{i=1}^n\lambda_i=1,\quad\lambda_i\ge 0,\quad i=1,\ldots,n. \end{align} where $\mathbb{1}$ is the vector of all ones. The unknowns are $\epsilon$ and all $\lambda_i$, the distance is $\epsilon_{\min}$.


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.