Danh mục Tài liệu số Thư viện

Một thuật toán hiệu quả cho bài toán tìm cặp điểm khác màu gần nhất trong tập điểm hai màu trên mặt phẳng

Bài toán tập điểm hai màu trong mặt phẳng được phát biểu như sau : “Cho n điểm màu xanh và m điểm màu đỏ trên mặt phẳng, làm thế nào tìm được cặp điểm xanh – đỏ gần nhau nhất”. Việc xác định lời giải cho bài toán này có thể được thực hiện tương đối dễ dàng bằng thuật toán vét cạn – kiểm tra hết tất cả các cặp điểm khác màu. Tuy nhiên, trong bài báo này chúng tôi sẽ trình bày một thuật toán tốt hơn rất nhiều để giải quyết bài toán này. Công cụ chủ yếu được sử dụng trong thuật toán của chúng tôi là lược đồ Voronoi trên mặt phẳng.

Từ khóa: Bài toán tìm cặp điểm khác màu, Tìm cặp điểm khác màu gần nhất, Tập điểm hai màu trên mặt phẳng, Lược đồ Voronoi trên mặt phẳng, Thuật toán vét cạn