I. Tập Lồi Trực Giao và Bao Lồi Trực Giao của Một Tập Trong Mặt Phẳng Số
Trong chương này, khái niệm về tập lồi và bao lồi được giới thiệu. Một tập S trong không gian Rn được gọi là lồi nếu nó chứa mọi đoạn thẳng nối hai điểm bất kỳ của nó. Điều này có nghĩa là nếu x và y thuộc S, thì mọi tổ hợp lồi của x và y cũng phải thuộc S. Bao lồi của một tập S là giao của tất cả các tập lồi chứa S, tức là tập lồi nhỏ nhất chứa S. Đặc biệt, bao lồi của một tập hữu hạn điểm trong Rn là một đa giác lồi. Việc hiểu rõ về tập lồi và bao lồi là rất quan trọng trong việc nghiên cứu các bài toán hình học tính toán, đặc biệt là trong việc tìm kiếm bao lồi trực giao. Tập lồi trực giao được định nghĩa là tập hợp S ⊂ R2 mà giao của nó với mọi đường thẳng đứng và mọi đường nằm ngang là một tập lồi. Điều này có nghĩa là tập lồi trực giao có thể không liên thông, và việc xác định các tính chất của nó là cần thiết để áp dụng trong các bài toán thực tiễn.
1.1 Tập Lồi và Bao Lồi của Một Tập
Định nghĩa về tập lồi và bao lồi được trình bày rõ ràng. Một đoạn thẳng nối hai điểm a và b trong Rn là tập hợp tất cả các điểm x có dạng {x ∈ Rn | x = (1 − λ)a + λb, 0 ≤ λ ≤ 1}. Tập S được gọi là lồi nếu nó chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Bao lồi của một tập S là giao của tất cả các tập lồi chứa S, và bao lồi của một tập hữu hạn điểm trong Rn là một đa giác lồi. Việc xác định bao lồi có ý nghĩa quan trọng trong nhiều ứng dụng thực tiễn, từ nhận dạng mẫu đến xử lý hình ảnh. Các định nghĩa và tính chất này sẽ được áp dụng trong các chương tiếp theo để giải quyết bài toán tìm bao lồi trực giao.
II. Thuật Toán Tìm Bao Lồi Trực Giao
Chương này trình bày thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya để tìm bao lồi trực giao của một đa giác lưới trong mặt phẳng số. Thuật toán này sử dụng các quy tắc phân loại điểm lưới dựa trên số ô có một đỉnh nằm trong đa giác lưới. Các điểm lưới được phân loại thành các lớp khác nhau, từ không có ô nào nằm trong đa giác đến các đỉnh 90 và 270 độ. Việc phân loại này giúp xác định các đỉnh và cạnh của bao lồi trực giao. Đặc biệt, thuật toán này có khả năng xử lý nhanh chóng nhờ vào việc chỉ sử dụng phép so sánh và cộng, trừ các số nguyên, với thời gian chạy O(n). Điều này làm cho thuật toán trở nên hiệu quả trong việc tìm kiếm bao lồi cho các tập hợp lớn. Các quy tắc loại bỏ vùng lõm cũng được áp dụng để đảm bảo tính chất lồi trực giao của bao lồi được duy trì.
2.1 Các Quy Tắc Tìm Bao Lồi Trực Giao
Các quy tắc tìm bao lồi trực giao được thiết kế để xử lý các đỉnh loại 1 và loại 3 trong quá trình di chuyển quanh biên của đa giác lưới. Quy tắc R11, R12 và R13 được áp dụng để loại bỏ các vùng lõm xuất hiện khi có hai đỉnh loại 3 liên tiếp. Mỗi quy tắc có điều kiện cụ thể về độ dài các cạnh và hướng di chuyển, giúp đảm bảo rằng bao lồi trực giao thu được không vi phạm tính chất lồi. Việc áp dụng các quy tắc này trong thuật toán giúp tối ưu hóa quá trình tìm kiếm và đảm bảo tính chính xác của kết quả. Thuật toán này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như xử lý hình ảnh và robot tự động.
