Cách đơn giản nhất để kiểm tra nếu điểm P nằm bên trong vỏ lồi được tạo thành bởi một tập hợp các điểm X?Tìm một điểm nằm bên trong thân lồi cho một tập hợp các điểm mà không cần tính toán thân tàu
Tôi muốn một thuật toán hoạt động trong không gian chiều cao (ví dụ: tối đa 40 thứ nguyên) không tính toán chính xác thân lồi. Ý tưởng nào?
Bạn không phải tính toán thân lồi, vì nó có vẻ khá rắc rối trong không gian đa chiều. Có một well-known property of convex hulls:
Bất kỳ vector (điểm) v bên trong thân tàu lồi của các điểm [v1, v2, .., vn] có thể được trình bày như sum(ki*vi), nơi 0 <= ki <= 1 và sum(ki) = 1. Tương ứng, không có điểm nào ngoài vỏ lồi sẽ có đại diện như vậy.
Trong không gian m chiều, điều này sẽ cung cấp cho chúng tôi bộ m phương trình tuyến tính với n các ẩn số.
chỉnh sửa
Tôi không chắc chắn về tính phức tạp của vấn đề mới này trong trường hợp tổng quát, nhưng đối với m = 2 có vẻ như tuyến tính. Có lẽ, ai đó có nhiều kinh nghiệm trong lĩnh vực này sẽ sửa tôi.
Trên thực tế trong không gian m-chiều bạn chỉ cần m + 1 điểm vì định lý Carathéodory: http://en.wikipedia.org/wiki/Carathéodory's_theorem_(convex_hull) Khó khăn là findind mà m + 1 điểm làm việc. – lhf
@ lhf Đó là một lưu ý tốt, mặc dù nó không ảnh hưởng đến tính chính xác của câu trả lời (và nó không rõ ràng làm thế nào để áp dụng nó để giải các phương trình). –
Vấn đề là đại số tuyến tính sẽ dễ dàng cung cấp cho bạn một không gian n chiều của các giải pháp cho phương trình của bạn, nhưng không cung cấp cho bạn bất kỳ cách dễ dàng nào để thỏa mãn sự bất bình đẳng. Do đó định lý bạn trích dẫn là một cách tốt để chỉ ra rằng một điểm nằm trong phần lồi của m + 1 điểm, nhưng đối với một tập hợp lớn hơn các điểm bạn cần tìm tập hợp đúng của m + 1 điểm để sử dụng định lý đã nói . Có n chọn m + 1 bộ như vậy để thử. Trong 40 kích thước sẽ là một vấn đề. – btilly
Bạn có sẵn sàng chấp nhận câu trả lời phỏng đoán mà thường hoạt động nhưng không được đảm bảo? Nếu bạn là sau đó bạn có thể thử ý tưởng ngẫu nhiên này. Để cho f (x) là khối lập phương của khoảng cách đến P lần số thứ trong X, trừ đi tổng của các khối của khoảng cách đến tất cả các điểm trong X. Bắt đầu một nơi nào đó ngẫu nhiên, và sử dụng một ngọn đồi leo thuật toán để tối đa hóa f (x) cho x trong một quả cầu rất xa P. Ngoại trừ trường hợp thoái hóa, nếu P không nằm trong thân lồi, nên có xác suất rất tốt để tìm kiếm bình thường đối với siêu phẳng mà P là ở một bên, và mọi thứ trong X nằm ở phía bên kia.
Điểm nằm bên ngoài thân lồi của các điểm khác nếu và chỉ khi hướng của tất cả vectơ từ điểm đó đến các điểm khác nằm dưới một nửa vòng tròn/hình cầu/xung quanh xung quanh nó.
Điều đó có vẻ giống như một giải pháp' O (m * n^2) 'tốt đẹp!+1 –
Mặc dù vậy, thuộc tính thứ hai sẽ rất khó để kiểm tra kích thước 'm'. Không dễ hơn việc giải phương trình tuyến tính 'm'. –
đây thực sự là một thuật toán rất tốt. Để kiểm tra "trên dưới 1/2 của một hypersphere" bạn kiểm tra các sản phẩm dấu chấm giữa hai hướng và xem nếu có bất kỳ 2 là tiêu cực (tức là theo hướng ngược lại). hoặc tôi có bỏ lỡ bất cứ điều gì không? –
Sự cố có thể được giải quyết bằng cách tìm điểm khả thi của Chương trình tuyến tính. Nếu bạn quan tâm đến chi tiết đầy đủ, trái ngược với việc chỉ cần cắm một LP vào bộ giải hiện có, tôi khuyên bạn nên đọc Chương 11.4 trong Boyd and Vandenberghe's excellent book on convex optimization.
Set A = (X[1] X[2] ... X[n]), có nghĩa là, cột đầu tiên là v1, thứ hai v2 vv
Giải quyết các vấn đề LP sau,
minimize (over x): 1
s.t. Ax = P
x^T * [1] = 1
x[i] >= 0 \forall i
nơi
x^T là transpose của x[1] là véc tơ tất cả-1.Vấn đề có giải pháp là điểm nằm trong thân lồi.
Có bất kỳ triển khai nào trong số này không? Tôi đang gặp khó khăn trong việc xây dựng mã này. –
Bạn sử dụng bộ giải mã LP nào? http://lpsolve.sourceforge.net/5.5/ là một trình giải mã LP nguồn mở khá dễ sử dụng. EDIT: không nhận ra bạn đang tìm kiếm toàn bộ shebang; Tôi không biết bất kỳ gói nào như vậy, thật không may. – user1071136
Tôi thực sự lập trình điều này trong trình duyệt, vì vậy tôi hiện đang sử dụng http://numericjs.com/documentation.html - Tôi chỉ gặp khó khăn khi thực hiện các phép biến đổi thành các bất bình đẳng. Có bất kỳ ví dụ nào ở đây http://www.joyofdata.de/blog/testing-linear-separability-linear-programming-r-glpk/ nhưng tôi không quen thuộc với R vì vậy tôi vẫn gặp sự cố! –
Tôi gặp vấn đề tương tự với 16 thứ nguyên.Vì ngay cả qhull cũng không hoạt động chính xác vì quá nhiều khuôn mặt phải được tạo ra, tôi đã phát triển phương pháp tiếp cận của riêng mình bằng cách kiểm tra, cho dù có thể tìm thấy siêu kết nối tách biệt giữa điểm mới và dữ liệu tham chiếu (tôi gọi đây là "HyperHull";)) .
Vấn đề tìm kiếm siêu phân tách có thể được chuyển thành vấn đề lập trình bậc hai lồi (xem: SVM). Tôi đã làm điều này trong python bằng cách sử dụng cvxopt với ít hơn 170 dòng mã (bao gồm cả I/O). Thuật toán hoạt động mà không cần sửa đổi trong bất kỳ thứ nguyên nào ngay cả khi có tồn tại vấn đề, khi kích thước càng cao thì số điểm trên thân tàu càng cao (xem: On the convex hull of random points in a polytope). Vì thân tàu không được xây dựng một cách rõ ràng nhưng chỉ được kiểm tra, cho dù một điểm có ở trong hay không, thuật toán có lợi thế rất lớn trong các kích thước cao hơn so với ví dụ: thân tàu nhanh.
Thuật toán này có thể 'tự nhiên' được song song và tăng tốc phải bằng số lượng bộ xử lý.
Nếu bạn có thể thực hiện triển khai hoặc một phần của nó trên github nó sẽ được đánh giá cao bởi nhiều người Tôi tin (http://www.mathworks.com/matlabcentral/answers/77363-very-high-dimensional-convex-hulls). Có lẽ đối với bạn nó có vẻ rất đơn giản. – j13r
Mặc dù bài đăng gốc là ba năm trước, có lẽ câu trả lời này sẽ vẫn trợ giúp. Thuật toán Gilbert-Johnson-Keerthi (GJK) tìm thấy khoảng cách ngắn nhất giữa hai đa giác lồi, mỗi cái được định nghĩa là thân lồi của một bộ máy phát --- đáng chú ý là bản thân thân lồi không phải được tính toán. Trong một trường hợp đặc biệt, đó là trường hợp được hỏi về, một trong những polytopes chỉ là một điểm. Tại sao không thử sử dụng thuật toán GJK để tính toán khoảng cách giữa P và phần lồi của các điểm X? Nếu khoảng cách đó là 0, thì P là bên trong X (hoặc ít nhất là trên ranh giới của nó). Triển khai GJK trong Octave/Matlab, được gọi là ClosestPointInConvexPolytopeGJK.m, cùng với mã hỗ trợ, có sẵn tại http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html. Một mô tả đơn giản về thuật toán GJK có sẵn trong Sect. 2 giấy, tại http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf. Tôi đã sử dụng thuật toán GJK cho một số bộ X rất nhỏ trong không gian 31 chiều và có kết quả tốt. Làm thế nào hiệu suất của GJK so sánh với các phương pháp lập trình tuyến tính mà những người khác đang đề xuất là không chắc chắn (mặc dù bất kỳ so sánh nào sẽ là thú vị). Phương pháp GJK không tránh tính toán vỏ lồi, hoặc thể hiện thân tàu về mặt bất bình đẳng tuyến tính, cả hai đều có thể tốn thời gian. Hy vọng câu trả lời này sẽ giúp.
Có lý do cụ thể nào bạn muốn thực hiện việc này không? Tính toán vỏ lồi không phải là rất tốn kém (O (n lg n)) và đơn giản hóa rất nhiều vấn đề. – templatetypedef
@templatetypedef: Tính toán vỏ lồi không phải là rất tốn kém trong 2 chiều. Nhưng nó sẽ đắt hơn theo cấp số nhân khi bạn tăng số lượng kích thước. Bạn không muốn làm điều đó cho một vấn đề 40 chiều. – btilly
Có lẽ câu hỏi này sẽ phù hợp hơn với [mathoverflow] (http://mathoverflow.com)? – wich