선체 자체를 계산하지 않고 점 집합에 대한 convex hull 내부에 점이 있는지 확인합니다.

Question

점 P가 점 집합 X로 형성된 볼록 선의 내부에 있는지 테스트하는 가장 간단한 방법은 무엇입니까?

저는 볼록 선체 자체를 명시 적으로 계산하지 않는 고차원 공간 (예 : 최대 40 차원)에서 작동하는 알고리즘을 원합니다. 어떤 아이디어?

Answer 1

다차원 공간에서 상당히 번거로운 것처럼 볼록 선체 자체를 계산할 필요가 없습니다. sum(ki*vi) 여기서 0 <= ki <= 1 및 sum(ki) = 1로 제시 할 수있다 점 [v1, v2, .., vn]의 볼록 선체 내부

모든 벡터 (점) v하십시오 well-known property of convex hulls이있다. 대응하여, 볼록 선체 밖의 어떤 점도 그러한 표현을 가질 수 없습니다.

m 차원 공간에서 n 알 수없는 m 선형 방정식 집합을 제공합니다.

편집
나는 일반적인 경우에서이 새로운 문제의 복잡성에 대해 잘 모르겠지만, m = 2 것이 선형 보인다. 아마,이 분야에서 더 많은 경험을 가진 누군가 나를 교정 할 것입니다.

Answer 2

일반적으로 작동 할만하지만 보장 할 수없는 경험적 답변을 기꺼이 받아 들일 의향이 있습니까? 그렇다면이 임의의 아이디어를 시도해 볼 수 있습니다.

X의 모든 요소에 대한 거리의 3 분의 합을 빼고 X에있는 요소의 수를 P 배에 곱한 거리의 입방체를 f (x)라고하고, 임의의 어딘가에서 시작하여 언덕을 사용하십시오 P에서 멀리 떨어져있는 구에서 x에 대해 f (x)를 최대화하기위한 등산 알고리즘. 퇴보 한 경우를 제외하고 P가 볼록 선체에없는 경우 P는 초평면에 대한 법선을 찾을 확률이 매우 높아야합니다. 한 쪽은 X, 다른 쪽은 X에있는 모든 것입니다.

Answer 3

점은 그 점에서 다른 점까지의 모든 벡터의 방향이 그 주위의 원/구/초 피쉬의 절반보다 작은 경우에만 다른 점의 볼록 선보다 바깥에 있습니다.

Answer 4

문제는 선형 프로그램의 실현 가능한 점을 찾아 냄으로써 해결할 수 있습니다. 기존의 솔버에 LP를 연결하는 것과는 대조적으로 자세한 내용에 관심이 있다면 Boyd and Vandenberghe's excellent book on convex optimization에서 11.4 장을 읽는 것이 좋습니다.

1. x^T는 전치이며

   세트 A = (X[1] X[2] ... X[n]) 즉, 첫 번째 열 v1이고, 상기 제 v2 등 다음 LP 문제를 해결

   ,

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

   x

2. [1]은 모두 1 벡터입니다.

문제는 점이 볼록한 선체에있는 경우 해결 방법이 있습니다.

Answer 5

16 개의 치수에서 동일한 문제가있었습니다.너무 많은 얼굴을 생성해야했기 때문에 qhull도 제대로 작동하지 않았기 때문에 필자는 새로운 초 점과 참조 데이터 사이에 분리 초평면을 찾을 수 있는지 테스트하여 직접 접근 방식을 개발했습니다 (이를 "HyperHull"이라고 함)) .

초평면 차 볼록 프로그래밍 문제로 변환 될 수있는 분리하는를 찾는 문제는 (참조 : SVM). 나는 파이썬에서 cvxopt를 사용하여 170 줄 이하의 코드 (I/O 포함)를 사용했다. 이 알고리즘은 문제가 존재하더라도 모든 차원에서 수정없이 작동하며, 선체의 점 수를 높이는 차원이 높습니다 (참조 : On the convex hull of random points in a polytope 참조). 선체가 명시 적으로 구성되지는 않았으므로 점만 내부에 있는지 여부에 관계없이 알고리즘은 예를 들어 점에 비해 매우 큰 차원에서 매우 큰 장점이 있습니다. 빠른 선체.

이 알고리즘은 "천연"및 병렬 프로세서의 수와 같아야 가속화 될 수있다. 원래 포스트는 3 년 전 이었지만

Answer 6

, 어쩌면이 대답은 여전히 ​​도움이 될 것입니다. Gilbert-Johnson-Keerthi (GJK) 알고리즘은 두 볼록 다각형 사이의 최단 거리를 찾는데, 각각은 생성기 집합의 볼록한 선체로 정의됩니다. 특히 볼록 선체 자체는 계산할 필요가 없습니다. 특수한 경우에 대해 질문하는 경우가 있는데, 폴리토프 중 하나는 하나의 요점에 불과합니다. 왜 GJK 알고리즘을 사용하여 P와 점 X의 볼록 선체 사이의 거리를 계산해 볼까요? 그 거리가 0이면 P는 X 내부 (또는 적어도 경계에 있음)입니다. 지원 코드와 함께 ClosestPointInConvexPolytopeGJK.m이라는 Octave/Matlab의 GJK 구현은 http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html에서 사용할 수 있습니다. GJK 알고리즘에 대한 간단한 설명은 Sect. 2, 논문 번호 : http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf. 저는 31 차원 공간에서 매우 작은 세트 X에 대해 GJK 알고리즘을 사용했으며 좋은 결과를 얻었습니다. GJK의 성능이 다른 사람들이 추천하는 선형 프로그래밍 방법과 비교하면 (어떤 비교가 흥미로울지라도) 불확실하다. GJK 방법은 볼록 선체를 계산하거나 선형 불평등의 관점에서 선체를 표현하는 것을 피하는데, 둘 다 시간 소모적 일 수 있습니다. 희망이 답변은 도움이됩니다.