Tìm ba điểm gần nhất mỗi điểm trên mặt phẳng 2D

Question

Bạn được cung cấp một danh sách các điểm trên mặt phẳng, viết chương trình xuất mỗi điểm cùng với ba điểm khác gần nhất là cho nó. Ba điểm này được sắp xếp theo khoảng cách.

Ví dụ, cho một tập hợp các điểm trong đó mỗi dòng có dạng: ID tọa độ x y phối hợp

1 0.0 0.0 
2 10.1 -10.1 
3 -12.2 12.2 
4 38.3 38.3 
5 79.99 179.99 

chương trình của bạn nên đầu ra:

1 2,3,4 
2 1,3,4 
3 1,2,4 
4 1,2,3 
5 4,3,1 

Đây là một câu hỏi phỏng vấn tôi tìm thấy trên Diễn đàn trực tuyến. Tôi có thể nghĩ ra một giải pháp O (n * n): tính toán khoảng cách của mỗi điểm đến mọi điểm khác. Trả về các điểm khoảng cách tối thiểu cho điểm này. Lặp lại quá trình cho các điểm khác

Answer 1

Bạn có thể muốn xem xét các cấu trúc dữ liệu không gian như cây k-d hoặc cây quad, đảm bảo thời gian dự kiến ​​tuyệt vời cho các tìm kiếm lân cận gần nhất. Ví dụ, cây k-d có thể thực hiện tìm kiếm lân cận gần nhất trong O (n) thời gian xấu nhất và O (sqrt N) dự kiến ​​thời gian sau khi thực hiện công việc tiền xử lý O (n log n).

Ngoài ra, nếu bạn biết rằng các điểm được phân phối ngẫu nhiên chủ yếu, bạn có thể xem xét phân vùng không gian vào tập hợp các nhóm có kích thước cố định. Để tìm những người hàng xóm gần nhất đến một điểm, bạn có thể xem tất cả các điểm trong cùng một nhóm, sau đó tất cả các điểm trong các nhóm lân cận, v.v. Điều này sẽ gần với thời gian O (n/b) mỗi điểm nếu các điểm này là độc đáo phân phối và có b nhóm.

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

Answer 2

gì họ đang tìm kiếm là nếu bạn đã bao giờ nghe nói về Delaunay triangulation, mà sau đó dẫn đến một O (n log n) thuật toán.

Chỉnh sửa. Nó không phải là đơn giản như tôi ngụ ý, theo sự điều chỉnh trong các ý kiến. Một thể sử dụng Delaunay triangulation để tìm ra ba người hàng xóm gần nhất trong O (n log n) thời gian, nhưng nó đòi hỏi một chút về công việc, như được giải thích trong bài viết bằng cách Dickerson, Drysdale và Sack, "Simple Algorithms for Enumerating Interpoint Distances and Finding k Nearest Neighbors".