Tìm điểm mà tổng khoảng cách để thiết lập các điểm khác là tối thiểu

Question

Tôi có một bộ (X) điểm (không phải là rất lớn, hãy nói 1-20 điểm) và điểm thứ hai (Y), lớn hơn nhiều. Tôi cần chọn một số điểm từ Y mà tổng khoảng cách đến tất cả các số từ X là tối thiểu.

Tôi đưa ra ý tưởng rằng tôi sẽ coi X là một đỉnh của đa giác và tìm thấy trọng tâm của đa giác này, và sau đó tôi sẽ chọn một điểm từ Y gần nhất với trọng tâm. Nhưng tôi không chắc liệu centroid có giảm thiểu tổng khoảng cách của nó đến các đỉnh của đa giác hay không, vì vậy tôi không chắc liệu đây có phải là một cách tốt hay không? Có bất kỳ thuật toán nào để giải quyết vấn đề này không?

Điểm được xác định theo tọa độ địa lý.

Answer 1

Centroid của đa giác có thể không đúng, nhưng vẫn tồn tại một điểm như vậy.

Trong giấy: n-ellipses and the minimum distance problem, nó được hiển thị rằng nếu điểm (gọi là tiêu điểm, thiết lập của bạn X) không được thẳng hàng rồi

• Có một điểm duy nhất (gọi là trung tâm) mà tổng khoảng cách được giảm thiểu. Điểm này là như vậy mà tổng của các đơn vị vectơ từ điểm đó đến foci là số không!

• Các locus của điểm mà tổng khoảng cách là hằng số là một đường cong lồi (gọi là n-elip) chứa trung tâm

• Các n-elip cho khoảng cách D hoàn toàn chứa n-elip cho bất kỳ khoảng cách D khác mà D '< D.

vì vậy bạn có thể làm một số loại thuật toán đồi leo núi để tìm trung tâm.

Tất nhiên, các dấu ba chấm này không nhất thiết là hình tròn, do đó, việc chọn điểm gần với trung tâm nhất có thể không hoạt động, nhưng có thể là một phép tính gần đúng.

Bạn có thể thực hiện một số tiền xử lý trên 20 điểm (nếu chúng được cố định) để tìm ra một lược đồ phân vùng tốt (dựa trên thông tin trên).

Hy vọng điều đó sẽ hữu ích.

Answer 2

Nếu bạn muốn giảm thiểu tổng các bình phương của khoảng cách (không phải là tổng các khoảng cách), thì thời điểm đó giảm thiểu số tiền đó là mức trung bình của các điểm trong X.

Proof:

sum(squares of distances) = (x-x0)^2 + (y-y0)^2 + (x-x1)^2 + (y-y1)^2 + ... 

d/dx sum(squares of distances) = 2(x-x0) + 2(x-x1) + ... = 2(Nx - x0 - x1 - ...) 

tổng được giảm thiểu khi phái sinh là zero, mà xảy ra khi Nx = x0+x1+..., vì vậy x = (x0+x1+...)/N

các phái sinh là đối xứng xung quanh thời điểm này, và các chức năng là bậc hai, vì vậy tôi khá chắc chắn rằng poin gần nhất t trong Y đến điểm trung bình này là tốt nhất.

Giảm thiểu khoảng cách khó hơn, nhưng tôi nghi ngờ cùng một thuật toán, với nhiều thời gian hơn trong tập hợp các Y mà bạn kiểm tra, cũng sẽ hoạt động.

Answer 3

Bởi vì bạn muốn tổng khoảng cách tối thiểu tôi tin rằng bạn có thể giảm tập hợp các điểm X xuống mức trung bình không gian của nó. Sau đó, bạn có thể sử dụng cây KDTree hoặc một số loại cây phân vùng không gian để tìm điểm trong Y gần nhất với trung bình không gian của X. Sử dụng cây phân đoạn không gian có thể tiết kiệm một chút công việc so với kiểm tra tất cả các điểm có thể.

Answer 4

Xin lỗi vì đã đề xuất sức mạnh vũ phu. Cách đặt câu hỏi được đặt ra là chúng ta không biết X, Y nằm ở đâu. Giả sử X là 30 điểm, Y là 1000 điểm. Sau đó, cho mỗi điểm của Y tổng cộng 30 khoảng cách. Tổng cộng 30000 phép tính, được thực hiện nhanh chóng. Điều này đảm bảo mức tối thiểu. Tìm một số "trung tâm" của X và chọn Y gần nhất sẽ là giải pháp gần đúng.

Câu hỏi thú vị hơn là tìm điểm như vậy cho riêng X. bỏ qua Y. Đối với X ba điểm duy nhất, điểm Fermat-Torichelli giải quyết được vấn đề.