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. | 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 Taïp chí KHOA HOÏC ÑHSP Nguyeãn Ngoïc Trung, Traàn Thò Dieäu Huyeà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 Nguyễn Ngọc Trung*, Trần Thị Diệu Huyền† 1. Mở đầu 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() 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 ? Chúng ta thấy rằng, trong chuyên ngành hình học tính toán, lược đồ Voronoi đóng một vai trò rất quan trọng trong việc giải quyết các bài toán tìm các cặp điểm gần nhất trên mặt phẳng. Điều này cũng dễ hiểu vì lược đồ Voronoi có những tính chất rất đặc trưng về khoảng cách, điều mà rất hay được dùng để rút ngắn thời gian tính toán, cũng như thời gian thực hiện các thuật toán giải những bài toán trên. Chính vì thế trong bài báo này, chúng tôi đã chọn lược đồ Voronoi để làm công cụ xây dựng thuật toán giải bài toán tìm cặp điểm khác màu gần nhất trong số tập điểm hai màu trên mặt phẳng. Cấu trúc bài báo như sau : mục 2 dành cho việc giới thiệu sơ lược về lược đồ Voronoi và các tính chất của nó. Phần mô tả chi tiết về thuật toán giải quyết bài toán sẽ được trình bày trong mục 3. Phần cuối của bài báo sẽ là một số chứng * ThS, Khoa Toán – Tin học, Trường Đại học Sư phạm † CN, Sinh viên Khoa Toán – Tin học Trường ĐHSP .
