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

Tóm tắt

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 thuộc dạng các bài toán tìm các cặp điểm gần nhất trong mặt phẳng. Bài toán đặt ra là : “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”. Bài toán trên có thể được giải một cách dễ dàng bằng cách lấy lần lượt từng cặp phần tử là các điểm xanh và và điểm đỏ, xác định khoảng cách giữa chúng và chọn ra cặp có khoảng cách nhỏ nhất. Thuật toán như vậy sẽ có độ phức tạp là O(n.m) trong đó n là số điểm xanh và m là số điểm đỏ trên mặt phẳng. Một câu hỏi được đặt ra là liệu có thể xây dựng một thuật toán tốt hơn cho bài toán này ?