Distancia al casco convexo

Question

Tengo $ n $ puntos $ x_1, \dots, x_n \in \Bbb R^d $. Dado un nuevo punto $ y $, ¿cómo puedo verificar que la distancia de $ y $ a la envolvente convexa de $ x_i $ es menor que un dado $ \varepsilon $? No es importante para mí si la distancia es euclidiana, cualquier norma $ p $ funcionaría. Estoy interesado en formas eficientes de calcular esto.

Como se solicitó, algunos detalles:

1. Empiezo a construir este grupo a partir de un solo punto, y añado puntos a él tan pronto como estén dentro de una distancia de $ \varepsilon $ de su envolvente convexa. De lo contrario, inicio un nuevo grupo y cierro el primero. Por lo general, los grupos son de un tamaño razonablemente pequeño (alrededor de $ 10 ^ 2 $ o $ 10 ^ 3 $ puntos), y el número total de puntos sin agrupar es de $ 10 ^ 5 $ o más.
2. La distribución de puntos es naturalmente agrupada, por lo que hay brechas decentes entre los puntos de datos.
3. El nuevo punto puede pertenecer tanto al interior como al exterior del grupo.
4. La evaluación de la distancia no tiene que ser precisa, esa es una de las razones por las que he mencionado que el uso de la norma $ p $ no importa realmente para mí.

Answer 1

Sin más indicaciones sobre restricciones, una solución básica sería precalcular una descomposición del casco convexo en una teselación de simplejos, luego calcular la distancia al casco convexo que es la mínima de las distancias de $y$ a cada simplejo.

Si $y$ no puede estar dentro del casco convexo, simplificaciones son posibles, como, considerar solo la distancia a la hiper-superficie del casco convexo.

Existen muchos algoritmos para construir tal teselación con diferentes eficiencias dependiendo de tu caso.

Existen muchas optimizaciones posibles al evaluar la distancia, por ejemplo, precalcular un espacio binario de partición.

Answer 2

Tomando la norma-$\max$, por ejemplo, el cálculo de la distancia es 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> donde $\mathbb{1}$ es el vector de todos unos. Los incógnitas son $\epsilon$ y todos los $\lambda_i$, la distancia es $\epsilon_{\min}.