Trouver si un point est à l'intérieur d'une coque convexe pour un ensemble de points sans calculer la coque elle-même

Question

Quel est le moyen le plus simple de tester si un point P est à l'intérieur d'une coque convexe formée d'un ensemble de points X? J'aimerais un algorithme qui fonctionne dans un espace de grande dimension (jusqu'à 40 dimensions, par exemple) qui ne calcule pas explicitement la coque convexe elle-même. Des idées?

Merci!

Answer 1

Le problème peut être résolu par la recherche d'un possible point d'un Programme Linéaire. Si vous êtes intéressé par les détails, plutôt que de simplement brancher un LP dans un solveur, je vous recommande la lecture du Chapitre 11.4 Boyd et Vandenberghe excellent ouvrage sur l'optimisation convexe.

Ensemble A = (X[1] X[2] ... X[n]), qui est, la première colonne est v1, le deuxième v2, etc.

Résoudre les suivantes problème LP,

minimize (over x): 1
s.t.     Ax = P
         x^T * [1] = 1
         x[i] >= 0  \forall i

où

1. x^T est la transposition de l' x
2. [1] est le 1 vecteur.

Le problème a une solution ssi le point est dans l'enveloppe convexe.

Answer 2

Le point se trouve en dehors de la coque convexe des autres points si et seulement si la direction de tous les vecteurs allant de celui-ci à ces autres points est sur moins de la moitié d'un cercle / sphère / hypersphère autour de lui.

Answer 3

Vous n'avez pas à calculer l'enveloppe convexe lui-même, comme il semble tout à fait ennuyeux dans des espaces multidimensionnels. Il y a bien connu propriété de convexe coques:

Tout vecteur (point) v à l'intérieur de l'enveloppe convexe des points de [v1, v2, .., vn] peut être présenté comme sum(ki*vi)où 0 <= ki <= 1 et sum(ki) = 1. En conséquence, aucun point à l'extérieur de l'enveloppe convexe aura une telle représentation.

Dans m-dimensions de l'espace, ce qui nous donnera l'ensemble de l' m des équations linéaires avec n inconnues.

modifier
Je ne suis pas sûr à propos de la complexité de ce nouveau problème dans le cas général, mais pour l' m = 2 il semble linéaire. Peut-être, quelqu'un avec plus d'expérience dans ce domaine me corriger.

Answer 4

J'ai eu le même problème avec 16 dimensions. Car même qhull ne fonctionne pas correctement car trop de visages devaient être généré, j'ai développé ma propre approche par les tests, si une séparation hyperplane peut être trouvé entre le nouveau point et les données de référence (je l'appelle "HyperHull" ;) ).

Le problème de trouver une séparation hyperplane peut être transformé en un problème de programmation quadratique convexe (voir: SVM). Je l'ai fait en python à l'aide de cvxopt, avec moins de 170 lignes de code (y compris les I/O). L'algorithme fonctionne sans modification dans n'importe quelle dimension, même s'il existe le problème, que plus la dimension que plus le nombre de points sur la coque (voir: Sur l'enveloppe convexe de points aléatoires dans un polytope). Depuis la coque n'est pas explicitement construit, mais seulement de contrôler si un point est à l'intérieur ou pas, l'algorithme a de très grands avantages dans les dimensions supérieures par rapport à par exemple rapide de la coque.

Cet algorithme peut "naturellement" être parallélisée et la vitesse doit être égal au nombre de processeurs.

Answer 5

Êtes-vous prêt à accepter une heuristique réponse qui devrait normalement fonctionner mais n'est pas garanti? Si vous êtes, alors vous pouvez essayer ce aléatoires idée.

Soit f(x) le cube de la distance à P fois le nombre de choses dans X, diminué de la somme des cubes de la distance de tous les points de la X. Commencer quelque part au hasard, et l'utilisation d'une colline d'escalade algorithme de maximiser f(x) pour x dans une sphère qui est très loin de la P. à l'Exception de cas dégénérés, si P n'est pas dans l'enveloppe convexe ce qui devrait avoir une très bonne probabilité de trouver la normale à un hyperplane laquelle P est sur un côté de, et tout ce que X est de l'autre côté de.