Đường dẫn và điểm phân loại ngắn nhất trong không gian 2 chiều

Question

Giả sử tôi có đối tượng trong không gian 2 chiều và một tập hợp các điểm mà tôi cần đối tượng đó để truy cập. Điểm có thể được thêm vào bất kỳ lúc nào, nhưng không được xóa.

Những gì tôi muốn là để có thể để xác định điểm gần nhất bên cạnh nơi mà đối tượng của tôi là trong thời gian O (lg (n)) thời gian, sau đó đi đến nó, sau đó xác định tiếp theo gần nhất, vv ..

Một hàng đợi ưu tiên đơn giản không làm việc cho điều này vì đối tượng đang thay đổi vị trí, do đó hàng đợi sẽ cần phải được sắp xếp lại mỗi khi nó di chuyển. Tôi đã tưởng tượng phân loại các điểm thành BST bằng cách nào đó, nhưng tôi không chắc chắn về cách sắp xếp theo (x, y) hoặc nếu nó thậm chí có thể.

Điều này có vẻ như tôi có thể đang cố gắng giải quyết traveling salesman mà không nhận ra điều đó, nếu có, tôi xin lỗi haha.

Answer 1

Một tùy chọn sẽ là sử dụng cây phân cách không gian như cây quadtree hoặc k-d để lưu trữ tất cả các điểm trong không gian. Những cấu trúc dữ liệu này có hiệu quả (thường trong thời gian sublinear) hỗ trợ các truy vấn dạng "điểm gần nhất với điểm p là gì?" Sau đó, bạn có thể làm như sau:

1. Tạo một cây phân cách không gian cho các điểm trong không gian.
2. Sử dụng cây để tìm điểm p gần điểm xuất phát nhất của bạn.
3. Lặp lại các bước sau:
   1. Di chuyển đến điểm p.
   2. Xóa p khỏi cây.
   3. Đặt p là điểm gần với vị trí hiện tại của bạn nhất.

Hy vọng điều này sẽ hữu ích!