Thuật toán để tìm tất cả các điểm trong tập A Một hàng xóm gần nhất trong bộ B

Question

Giả sử chúng ta có hai tập hợp điểm A, B và chúng tôi muốn tìm mọi điểm trong bộ A hàng xóm gần nhất trong bộ B.

Có nhiều thuật toán tốt để tìm hàng xóm gần nhất cho một điểm. Có cách nào để sử dụng thông tin chúng tôi nhận được cho a_1, để tìm kiếm hiệu quả hơn cho người hàng xóm gần nhất cho a_2 hoặc các điểm khác trong bộ này không?

Tôi đang suy nghĩ một cái gì đó như: sử dụng bất đẳng thức tam giác để có được một khoảng cách cho khoảng cách có thể giữa mỗi điểm trong B và điểm mới a_2, và sắp xếp tối đa và min của khoảng thời gian, và sau đó tôi có thể tìm kiếm chỉ các điểm trong B rơi vào khoảng đầu tiên.

Answer 1

1. Tìm Voronoi diagram cho điểm của bộ B.
2. Áp dụng một Sweep line algorithm qua điểm của tập A và sơ đồ Voronoi của bộ B. Bất cứ nơi nào dòng quét bao gồm một số điểm từ tập A, nhìn giữa mà cạnh của sơ đồ Voronoi này điểm nằm. Điều này cho phép xác định khuôn mặt của biểu đồ Voronoi thuộc điểm này. Cung cấp cho điểm gần nhất từ ​​bộ B.

Chi tiết cho bước 2: Giữ tất cả các cạnh của biểu đồ Voronoi, hiện đang bị cắt bởi đường quét, trong một số vùng chứa đã đặt hàng. Khi đường quét bao phủ một số đỉnh của sơ đồ Voronoi, hãy xóa/thêm cạnh, sự cố tới đỉnh này, từ/đến vùng chứa. Để xem xét, giữa các cạnh nào đó có một số điểm nào đó, hãy đặt các cạnh kế thừa/tiền thân cho điểm này trong vùng chứa.

Độ phức tạp thời gian là nhật ký O ((M + N) M). N = | A |, M = | B |.

Answer 2

Bạn có thể hưởng lợi từ việc đọc bentleys "viết các chương trình hiệu quả" nơi ông đề cập đến nghiên cứu điển hình về chương trình người bán hàng lưu động. Một trong những khoản tiết kiệm mà anh nhận ra là sự chênh lệch giữa hai điểm liên quan đến việc lấy một căn bậc hai đắt tiền. Lấy căn bậc hai cho bạn khoảng cách thực tế, không lấy căn bậc hai cho bạn một số có thể được sử dụng để so sánh với các giá trị tương đối khác.

Tôi đặc biệt khuyên bạn nên đọc sách. Nó sẽ đặt bộ não của bạn vào đúng nơi.

Answer 3

Một giải pháp lực lượng vũ phu có thể sử dụng biểu đồ hình chữ nhật của các điểm gần nhất của tập B. Sau đó so sánh từng điểm của tập A với chữ cái biểu đồ. Bạn cũng có thể tạo dendogram với một tam giác delaunay.