Luận văn Tìm bao lồi trực giao của một đa giác lưới trong mặt phẳng số

.., xk ∈ S thì x = k∑ j=1 λjx j, λj ≥ 0,∀j = 1, 2, ..., k, k∑ j=1 λj = 1. Giả sử λk > 0, đặt ξ = k−1∑ j=1 λj . Khi đó, 0 < ξ < 1 và x = k−1∑ j=1 λjx j + λkx k = ξ k−1∑ j=1 λj ξ xj + λkx k. Do k−1∑ j=1 λj ξ = 1 và λj ξ > 0 với mọi j = 1, 2, ..., k−1 nên theo giả thuyết quy nạp điểm 8y := k−1∑ j=1 λj ξ xj ∈ S. Ta có x = ξy + λkxk. Do ξ > 0, λk > 0 và ξ + λk = k∑ j=1 λj = 1 nên x là một tổ hợp lồi của hai điểm y và xk đều thuộc S. Vậy x ∈ S. Hình 1.2: Tập không lồi Mệnh đề 1.1.2. (xem [11]) Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm , thì các tập sau là lồi: A ∩B := {x|x ∈ A, x ∈ B}, αA+ βB := {x|x = αa+ βb, a ∈ A, b ∈ B,α, β ∈ R}, A× C := {x ∈ Rm+n|x = (a, c) : a ∈ A, c ∈ C}. Định nghĩa 1.1.3. 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. Nhận xét 1.1.1. Bao lồi của tập S là tập lồi nhỏ nhất chứa S. Bao lồi của một tập hữu hạn điểm P trong Rn là một đa giác lồi trong Rn. 1.2 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Ố Định nghĩa 1.2.1. (xem [12]) Một tập hợp S ⊂ R2 được gọi là lồi trực giao nếu giao của nó với mọi đường thẳng đứng và mọi đường nằm ngang là một tập 9lồi. Hình 1.3: Tập lồi trực giao (a), (b), (c) và tập không lồi trực giao (d), (e) Trong Hình 1.3, có ba tập là lồi trực giao ((a), (b), (c)) và hai tập không là lồi trực giao ((d), (e)) do giao của tập (d) này với đường nằm ngang nét đứt và tập (e) với đường thẳng đứng nét đứt là hai đoạn thẳng. Chú ý 1.2.1. Tập lồi trực giao có thể không liên thông. Ví dụ là tập (c) trong Hình 1.3. Nhận xét 1.2.1. (xem [12]) (Tính chất của tập lồi trực giao) (i) Giao của các tập lồi trực giao là một tập lồi trực giao. (ii) Mọi tập lồi đều là lồi trực giao. (iii) Một tập không liên thông là lồi trực giao nếu và chỉ nếu mọi thành phần liên thông của nó là lồi trực giao và không có đường thẳng đứng hoặc đường nằm ngang nào giao với hơn một thành phần liên thông của nó. Định nghĩa 1.2.2. (xem [12]) Bao lồi trực giao của một tập là giao của tất cả các tập lồi trực giao chứa tập đó. Hình 1.4 cho hai ví dụ về bao lồi trực giao của tập liên thông ((a), (b)) và hai ví dụ về bao lồi trực giao của tập không liên thông ((c), (d)). Nhận xét 1.2.2. (xem [12]) (Tính chất của bao lồi trực giao) 10 Hình 1.4: Bao lồi trực giao của một số tập (i) Bao lồi trực giao của một tập là tập lồi trực giao bé nhất chứa tập đó. (ii) Một tập là lồi trực giao nếu và chỉ nếu bao lồi trực giao của nó là chính nó. (iii) Bao lồi trực giao của một tập là một tập con của bao lồi của tập đó. Nhận xét 1.2.3. Bao lồi trực giao của một tập là duy nhất. Định nghĩa 1.2.3. (xem [9]) Một lướiG là một tập hợp gồm một số đường nằm ngang cách đều nhau, một số đường thẳng đứng cách đều nhau và tất cả các giao điểm của chúng, ở đó khoảng cách giữa hai đường nằm ngang liên tiếp và hai đường thẳng đứng liên tiếp là như nhau. Kích thước lưới g là khoảng cách giữa hai đường nằm ngang liên tiếp (hoặc hai đường thẳng đứng liên tiếp). Điểm lưới là điểm giao nhau của một đường nằm ngang và một đường thẳng đứng. Định nghĩa 1.2.4. Mặt phẳng số là mặt phẳng được gắn thêm một lưới. Định nghĩa 1.2.5. (xem [9]) P là một đa giác lưới khi nó là một đa giác có mỗi đỉnh là một điểm lưới và mỗi cạnh đều song song với một trong hai trục tọa độ. Trong luận văn này, với mục tiêu trình bày lại việc tìm bao lồi trực giao của một đa giác lưới, khi đó bao lồi trực giao của một đa giác lưới được định nghĩa như sau 11 Định nghĩa 1.2.6. (xem [9]) Bao lồi trực giao của một đa giác lưới S, kí hiệu OH(S), là đa giác lưới có diện tích nhỏ nhất sao cho (i) Mỗi điểm p ∈ S đều nằm trong OH(S). (ii) Giao củaOH(S) với bất kì đường nằm ngang hoặc đường thẳng đứng nào là rỗng hoặc là một đoạn thẳng duy nhất. 12 CHƯƠNG 2 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 TRONGMẶT PHẲNG SỐ Trong chương này, chúng ta xét bài toán tìm bao lồi trực giao của một đa giác lưới cho trước. Để giải bài toán này, nhóm của Biswas, Bhowmick, Sarkar và Bhattacharya đã xây dựng một số quy tắc sau đây. 2.1 CÁC QUY TẮC Cho q là một điểm lưới và một đa giác lưới S. Việc phân loại điểm lưới q dựa trên số ô có một đỉnh là q,Q1−Q4, nằm trong đa giác lưới S (ở đóQi là là góc phần tư thứ i, i = 1, . . . , 4) và sự sắp xếp của chúng (Hình 2.1). Hình 2.1: Các loại đỉnh khác nhau của một đa giác lưới Nếu số ô nằm trong đa giác lưới S là i, thì q được phân loại thành các lớp Ci như sau: 13 C0 : Không có ô nào nằm trong đa giác lưới. Khi đó, q không phải là một đỉnh. C1 : Chỉ có một ô nằm trong đa giác lưới (Hình 2.1 (a)). Khi đó q là một đỉnh của đa giác lưới S và được phân loại là một đỉnh 90. C2 : Có đúng hai ô nằm trong đa giác lưới. Trong trường hợp này có thể có hai cách sắp xếp khác nhau. (i) Hai ô đó nằm trong đa giác lưới là liền kề. Khi đó, q là một điểm cạnh (Hình 2.1 (d)). (ii) Hai ô nằm trong đa giác lưới là chéo nhau. Khi đó, q là một đỉnh 270 (Hình 2.1 (c)). Nhận xét, trong bốn cạnh có đầu mút là q sẽ có hai cạnh được sử dụng để xác định hướng di chuyển (qua q) để q trở thành một đỉnh 270. Ví dụ, nếu q là điểm cuối của một cạnh đi xuống, thì cạnh đi ra từ q sẽ hướng sang trái (đường nét liền). Tương tự, nếu q là điểm cuối của một cạnh đi lên, thì cạnh tiếp theo sẽ hướng sang phải (đường nét đứt). C3 : Có đúng ba ô nằm trong đa giác lưới (Hình 2.1 (b)). Khi đó q là một đỉnh của đa giác lưới S và q là một đỉnh 270. C4 : Tất cả bốn ô đều nằm trong đa giác lưới. Khi đó q không phải là một đỉnh. Như vậy, một điểm lưới có thể là một đỉnh hoặc không. Nếu điểm lưới q là một đỉnh của đa giác lưới, thì q có thể là một đỉnh 90 hoặc là một đỉnh 270. Ngược lại, nếu q không phải là một đỉnh, thì q có thể là một điểm trên cạnh của bao lồi trực giao, hoặc là một điểm nằm bên trong đa giác lưới, hoặc là nằm bên ngoài đa giác lưới. Do đó, trong luận văn này, một đỉnh loại 1 là một đỉnh 90 (1 ×90o) và một đỉnh loại 3 là một đỉnh 270 (3 ×90o) để dễ kí hiệu. Một đỉnh vi được biểu diễn bởi một bộ ba. Trong đó ti (=1 hoặc 3) là loại đỉnh, di là hướng di chuyển từ đỉnh vi đến đỉnh vi+1 và li là chiều dài đoạn đường (nằm ngang hoặc thẳng đứng) từ vi đến vi+1. Các hướng di chuyển di từ vi có thể có các giá trị 0, 1, 2 hoặc 3 cho biết tương ứng các hướng đi 14 sang phải, lên trên, sang trái hoặc xuống dưới. Hướng di chuyển di được xác định bởi hướng di chuyển trước đó di−1 (hướng di chuyển từ vi−1 đến vi) và loại đỉnh vi và được cho bởi công thức di = (di−1 + ti) mod 4. Khi di được tính toán, điểm lưới tiếp theo được xác định bởi loại của nó. Do đó, quá trình di chuyển từ vi đến vi+1 kết thúc khi trở về đỉnh bắt đầu. Để xác định đỉnh bắt đầu, chúng tôi giả sử rằng nó là điểm trên cùng bên trái p0(i0, j0) của đa giác lưới S. Điểm p0 là điểm trên cùng bên trái khi và chỉ khi với mỗi điểm p(i, j) ∈ S thì j i0. Khi đó tọa độ của điểm bắt đầu vs được cho bởi is = (di0/ge − 1)× g, js = (bj0/gc+ 1)× g (ở đây, g là kích thước lưới). Kiểu ts của đỉnh bắt đầu được xác định bởi số ô lân cận nằm trong đa giác lưới. Hướng bắt đầu từ vs được cho bởi công thức ds = (2 + ts) mod 4. Hình 2.2: Vùng lõm do hai đỉnh loại 3 liên tiếp, tạo ra nhiều đoạn thẳng với một đường thẳng đứng (trái) và một đường nằm ngang (phải) Trong quá trình di chuyển, nếu gặp hai đỉnh loại 3 liên tiếp, thì nó cho chúng ta biết có một vùng lõm xuất hiện và nó không thỏa mãn tính lồi trực giao. Ví dụ trong Hình 2.2 là hai mẫu như trên mà giao điểm của một đường thẳng đứng hoặc một đường nằm ngang l với đa giác lưới có nhiều hơn một đoạn. Do đó, mục tiêu của chúng ta là xác định những vùng như vậy và suy ra các cạnh của bao lồi trực giao sao cho các tính chất lồi trực giao được bảo đảm. Mặt khác, các mẫu 13, 31 và 11 không tạo thành vùng lõm và do đó không vi phạm các tính chất của lồi trực giao. Bởi vì lí do này nên trong thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya, bao lồi trực giao thu được khi không có hai 15 đỉnh loại 3 liên tiếp (mẫu 33) xuất hiện trong chuỗi danh sách các đỉnh (xem Chương 2, Mục 2.2). Cho v0, v1, v2, v3 và v4 là năm đỉnh liên tiếp mà cần phải sử dụng quy tắc để loại bỏ vùng lõm, trong đó v4 là đỉnh mới cập nhật còn bốn đỉnh v0 . . . v3 đã được cập nhật trước đó. Do quy tắc loại bỏ vùng lõm chỉ được áp dụng khi xuất hiện hai đỉnh loại 3 liên tiếp, Biswas, Bhowmick, Sarkar và Bhattacharya đã thiết kế hai bộ quy tắc tùy thuộc vào đỉnh tiếp theo mẫu 33 là 1 hay 3. Trong luận văn này, chúng tôi quy ước hai đỉnh loại 3 liên tiếp là v2 và v3, đỉnh v1 thuộc loại 1, đỉnh v0 có thể thuộc loại 1 hoặc cũng có thể thuộc loại 3. Đối với thuật toán này, Biswas, Bhowmick, Sarkar và Bhattacharya quy ước luôn bắt đầu từ một đỉnh loại 1. Sử dụng quy ước này để đảm bảo rằng luôn có một đỉnh loại 1 trước hai đỉnh loại 3 liên tiếp. Một đỉnh giả sẽ được đưa ra trước đỉnh bắt đầu để xử lí tình huống khi hai đỉnh loại 3 xuất hiện ngay sau đỉnh bắt đầu. Định nghĩa 2.1.1. [9] Mẫu 1331 là một mẫu biểu diễn một đỉnh loại 1, sau đó là hai đỉnh loại 3 liên tiếp, theo sau là một đỉnh loại 1. Hai đỉnh loại 3 liên tiếp trong mẫu 1331 cho chúng ta một vùng lõm. Để loại bỏ vùng lõm này, dựa vào mối quan hệ độ dài các cạnh l1 và l3, chúng ta có ba trường hợp dưới đây ([9]) (Hình 2.3, 2.4, 2.5): • Quy tắc R11 (Áp dụng khi l1 = l3) (Hình 2.3): Các đỉnh v1, v2, v3 và v4 bị loại bỏ và độ dài v0 được sửa lại thành l0 + l2 + l4. • Quy tắc R12 (Áp dụng khi l1 > l3) (Hình 2.4): Các độ dài l1 và l2 được sửa lại lần lượt là l1 − l3 và l2 + l4. Các đỉnh v3 và v4 bị loại bỏ. • Quy tắc R13 (Áp dụng khi l1 < l3) (Hình 2.5): Các đỉnh v1 và v2 bị loại bỏ. Các độ dài l0 và l3 được sửa lại lần lượt là l0 + l2 và l3 − l1. Chú ý 2.1.1. Trong ba quy tắc R11, R12, R13 loại t0 của đỉnh t0 vẫn không thay đổi, điều này đúng và không gây ra vấn đề khi v0 là đỉnh giả. 16 Hình 2.3: Quy tắc R11 cho mẫu 1331 Hình 2.4: Quy tắc R12 cho mẫu 1331 17 Hình 2.5: Quy tắc R13 cho mẫu 1331 Định nghĩa 2.1.2. [9] Mẫu 1333 là một mẫu biểu diễn một đỉnh loại 1, sau đó là ba đỉnh loại 3 liên tiếp. Để loại bỏ vùng lõm với mẫu này chúng ta có các quy tắc như sau ([9])(Hình 2.6, 2.7, 2.8): • Quy tắc R21 (Áp dụng khi l1 < l3) (Hình 2.6): Các đỉnh v1 và v2 bị loại bỏ. Các độ dài l0 và l3 được sửa lại lần lượt là l0 + l2 và l3 − l1. • Quy tắc R22 (Áp dụng khi l1 ≥ l3 và d = d2) (Hình 2.7): Bắt đầu từ đỉnh v4. Gọi v là đỉnh hiện tại đang xét. Gọi lH là đường nằm ngang đi qua v2, lV là đường thẳng đứng đi qua v4. Quy tắc chỉ được áp dụng khi v nằm dưới nửa mặt phẳng xác định bởi lH đồng thời nằm bên trái nửa mặt phẳng xác định bởi lV . Hai biến l′ và l” được khởi tạo với giá trị ban đầu lần lượt là l1 − l3 và l4 được dùng để xác định xem v có ra khỏi vùng lõm của mẫu này hay không. Độ dài l′ và l” được cập nhật dựa theo hướng đi của v. Nếu hướng đi từ v, kí hiệu là d, giống với hướng đi từ v1 (nghĩa là d = d1), thì l′ được cập nhật thành l′ = l′+ l. Ở đó l là độ dài đường đi từ v. Ngược lại, nếu hướng đi từ v giống với hướng đi từ v3 (nghĩa là d = d3), thì l′ được 18 cập nhật thành l′ = l′ − l. Tương tự, l” được cập nhật thành l” = l” + l nếu hướng đi từ v giống hướng đi từ v4 (nghĩa là d = d4) và l” = l” − l nếu hướng đi từ v giống hướng đi từ v2 (nghĩa là d = d2). Quá trình này được thực hiện cho đến khi l′ < l1 − l3 và l” < l2. Kết thúc quá trình độ dài l1 được cập nhật thành l′ và độ dài l2 được cập nhật thành l2 − l”. Các đỉnh v3 và v4 bị loại bỏ. • Quy tắc R23 (Áp dụng khi l1 ≥ l3 và d = d3) (Hình 2.8): Tương tự như luật R22, hai biến l′ và l” được khởi tạo. Quá trình này được thực hiện cho đến khi l′ < l1 − l3 và l” < l2. Kết thúc quá trình đỉnh v4 bị loại bỏ và độ dài l1, l2 và l3 lần lượt được cập nhật thành l1 = l1 − l3, l2 = l2 − l” và l3 = l1 − l3 − l′. Hình 2.6: Quy tắc R21 cho mẫu 1333 Chú ý 2.1.2. Mỗi quy tắc cho mẫu 1331 loại bỏ một vùng lõm tùy thuộc vào độ dài l1 và l3. Trong khi đó, mỗi quy tắc cho mẫu 1333 chỉ loại bỏ vùng lõm khi đỉnh cuối cùng ra khỏi vùng lõm đồng thời sử dụng toàn bộ độ dài l0, l1, l2, l3, l4. 19 Hình 2.7: Quy tắc R22 cho mẫu 1333 Hình 2.8: Quy tắc R23 cho mẫu 1333 20 Các quy tắc trên được phát hiện và áp dụng khi di chuyển xung quanh biên của đa giác lưới. Danh sách L được khởi tạo với một đỉnh giả. Quá trình bắt đầu từ đỉnh trên cùng bên trái của đa giác lưới. Trong quá trình, mỗi đỉnh mới được truy cập sẽ được thêm vào danh sách L. Sau đó, năm đỉnh cuối cùng trong danh sách của L sẽ được kiểm tra. Nếu xuất hiện vùng lõm thì một trong các quy tắc loại bỏ vùng lõm cho mẫu 1331 và 1333 được áp dụng, sau đó, một lần nữa năm đỉnh cuối cùng của L được kiểm tra. Nếu không, thêm đỉnh tiếp theo vào danh sách của L, sau đó kiểm tra năm đỉnh cuối cùng. Quá trình thực hiện cho đến khi đỉnh bắt đầu được xét đến lần thứ hai. Kết thúc thuật toán L là danh sách chứa các đỉnh của bao lồi trực giao. 2.2 THUẬT TOÁN Algorithm 1 Sơ lược về thuật toán Các bước: 1: Tìm đỉnh bắt đầu, vs 2: for (TRUE) do 3: Tìm đỉnh tiếp theo, vn 4: Cho đỉnh này vào danh sách L (Bắt đầu là tập rỗng) 5: if loại bốn đỉnh cuối trong danh sách L là mẫu 1331 then 6: áp dụng quy tắc R11, R12 hoặc R13 7: else 8: if loại bốn đỉnh cuối trong danh sách L là mẫu 1333 then 9: áp dụng quy tắc R21, R22 hoặc R23 10: while vn 6= vs Sơ lược về thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya được đưa ra trong Algorithm 1. Bắt đầu từ đỉnh vs. Trong vòng lặp do-while, đỉnh tiếp theo vn được xác định và cho vào danh sách L. Nếu bốn đỉnh cuối trong danh sách L có mẫu 1331 thì áp dụng một trong các quy tắc R11, R12, R13. Tương tự, một trong các quy tắc R21, R22, R23 được áp dụng khi bốn đỉnh 21 cuối cùng trong danh sách L có mẫu 1333. Vòng lặp do-while được tiếp tục cho đến khi cập nhật tới đỉnh vs lần hai. Algorithm 2 Thuật toán Otho-Hull(S, g, vs) Các bước: 1: L[1]← vd, k ← 2 2: L[k].d = ds, L[k].t = ts, ← 3: for (TRUE) do 4: ← Next-Vertex(S, i, j, L[k].d, g) 5: while (TRUE) do 6: if (k ≥ 5) then 7: if (L[k − 3]..L[k].t = 1331) then 8: k ← Apply-R1(L, k) 9: else 10: if (L[k − 3]..L[k].t = 1333) then 11: ← Apply-R2(L, k, i, j, g) 12: else break 13: k ← k + 1 14: L[k].d← d, L[k].t← t 15: while ( 6=) Thuật toán Otho-Hull [9] đưa ra danh sách sắp xếp các đỉnh của bao lồi trực giao của một đa giác lưới. Nó lấy đa giác lưới S, kích thước lưới g và đỉnh bắt đầy vs như là tham số đầu vào. Danh sách L được khởi tạo với một đỉnh giả vd. Độ dài cạnh từ vd được đặt bằng 0 và hướng đi của vd không có ý nghĩa trong thuật toán. Đỉnh giả là bắt buộc vì quy tắc luôn được áp dụng cho một chuỗi năm đỉnh. Một tình huống có thể xảy ra là vs luôn thuộc loại 1 và tiếp theo sau là hai đỉnh loại 3 và một đỉnh loại 1 dẫn đến mẫu 1331 và l1 > l3. Khi đó quy tắc R21 được áp dụng (trên năm đỉnh liên tiếp) trong đó yêu cầu một đỉnh giả. Trong mỗi lần vòng lặp do-while (Bước 3− 15), đỉnh tiếp theo được thêm vào L. Nếu danh sách L chứa nhiều hơn năm đỉnh (Bước 6), thì mẫu được hình thành bởi bốn đỉnh cuối cùng các đỉnh trong L được kiểm tra. Các đỉnh v4, v3, 22 v2, v1 và v0 được đề cập đến ở Mục 2.1 tương ứng với các đỉnh được biểu thị bởi L[k], L[k− 1], L[k− 2], L[k− 3] và L[k− 4], ở đó L[k] là đỉnh được truy cập gần nhất. Nếu mẫu ứng với loại của L[k]...L[k − 3] là 1331 thì quy tắc dùng để loại bỏ vùng lõm là áp dụng Apply-R1 [9] (Bước 7-8). Quy trình Apply-R1 trả về giá trị cập nhật của k. Tương tự, nếu mẫu ứng với dạng 1333 thì quy tắc dùng để loại bỏ vùng lõm là áp dụng Apply-R2 [9] (Bước 10-11). Apply-R2 trả về cho chúng ta k và . Nếu việc loại bỏ vùng lõm được thực hiện, thuật toán tiếp tục đánh giá bốn đỉnh cuối cùng sau khi loại bỏ (Bước 5-12) đế kiểm tra xem có giảm thêm không. Mặt khác, khi không có quy tắc nào được áp dụng (Bước 12) nó sẽ thoát ra vòng lặp While và đánh giá đỉnh tiếp theo. Biến k luôn luôn trỏ đến đỉnh cuối cùng của danh sách L và được tăng lên với lượt truy cập của mỗi đỉnh. Quy trình Next-Vertex [9] tính toán độ dài tương ứng với L[k]. Nó cũng tính hướng d và loại t của đỉnh tiếp theo. Giá trị của k được tăng lên ở bước 13 và d, t được chỉ định để tăng lên L[k]. Thuật toán kết thúc (Bước 15) khi tọa độ trùng với . Algorithm 3 Quy trình Next-Vertex(S, i, j, d, g) Các bước: 1: m← 0, r ← 0, l← 0 2: while (TRUE) do 3: (i, j)← d∗(i, j) 4: for h← 1 to 4 do 5: if Qh(i, j) ∩ S 6= ∅ then 6: m← m+ 1, r ← r + h 7: if r ∈ {4, 6} vàm = 2 then t← 3 8: else 9: ifm ∈ {0, 2, 4} then t← 0 10: else t← m 11: d← (t+ d) mod 4, l← l + g 12: if t 6= 0 then break 13: return 23 Trong quy trình Next-Vertex, trong vòng lặp While (Bước 2-12), đỉnh tiếp theo được tính từ đỉnh hiện tại . Các tọa độ của điểm lưới tiếp theo được xác định trong Bước 3. Bước 4-11 xác định xem điểm lưới có phải một đỉnh (loại 1 hoặc 3) hoặc một điểm cạnh hay không. Thuật toán tiếp tục đánh giá các điểm lưới tiếp theo cho đến khi đạt được đỉnh L[k + 1]. Khi thuật toán tiến tới đỉnh tiếp theo, chiều dài được tăng thêm bởi g (Bước 11). Quy trình cho ta loại và hướng của đỉnh L[k + 1] và chiều dài l từ đỉnh hiện tại L[k] đến đỉnh tiếp theo L[k + 1]. Các tọa độ của điểm lưới tiếp theo được tính (Bước 3) dựa trên hướng d từ (i, j). Nếu hướng di chuyển sang phải (d = 0) hoặc sang trái (d = 2) thì tọa độ y vẫn không thay đổi và tọa độ x được tăng (d = 0) hoặc giảm (d = 2) theo g. Nếu hướng di chuyển lên trên (d = 1) hoặc xuống dưới (d = 3) thì tọa độ y được giảm (d = 1) hoặc tăng (d = 3) trong khi tọa độ x giữ nguyên. Nói cách khác, với d = 0, ←; với d = 2, ←; với d = 1, ←; với d = 3, ←. Trong quy trình Apply-R1, nếu độ dài của các đỉnh L[k − 3] và L[k − 1] là giống nhau (Bước 1), thì độ dài của L[k − 4] được sửa lại như trong Bước 2. Phần đuôi của danh sách được đặt lại thành k − 4 (Bước 3) khi bốn đỉnh cuối cùng được xóa theo quy tắc R11, tương tự quy tắc R12 và R13 được thực hiện lần lượt theo Bước 4-8 và Bước 9-14. Trong khi áp dụng quy tắc R13, các đỉnh L[k − 3] (v1) và L[k − 2] (v2) bị xóa bỏ, các đỉnh L[k − 1] (v3) và L[k] (v4) được gán lại là L[k − 3] và L[k − 2] tương ứng (Bước 12-13). Đuôi của danh sách k được đặt lại thành k − 2 vì có hai đỉnh đã bị xóa (Bước 14). Giá trị của k được đặt lại tương ứng k − 4 (Bước 3) và k − 2 (Bước 8). Quy trình trả về và cập nhật cho chúng ta giá trị k trong Bước 15. Quy trình Apply-R2 thực hiện bộ quy tắc thứ hai cho mẫu 1333. Quy tắc R21 được áp dụng khi l1 < l3 (Bước 1-6). Mặt khác, khi l1 ≥ l3 (Bước 8), hai biến l′ và l” được khởi tạo (Bước 9). Vòng lặp While (Bước 11-19) được lặp lại miễn là điều kiện l′ ≥ l1− l3 hoặc điều kiện l” ≥ l2 còn thỏa mãn. Trong vòng lặp While, đỉnh tiếp theo được truy cập và các giá trị l′ và l” được sửa đổi tùy 24 Algorithm 4 Quy trình Apply-R1(L, k) Các bước: 1: if L[k − 3].l = L[k − 1].l then 2: L[k − 4].l← L[k − 4].l + L[k − 2].l + L[k].l 3: k ← k − 4 4: else 5: if L[k − 3].l > L[k − 1].l then 6: L[k − 3].l← L[k − 3].l − L[k − 1].l 7: L[k − 2].l← L[k − 2].l + L[k].l 8: k ← k − 2 9: else 10: L[k − 1].l← L[k − 1].l − L[k − 3].l 11: L[k − 4].l← L[k − 4].l + L[k − 2].l 12: L[k − 2]← L[k] 13: L[k − 3]← L[k − 1] 14: k ← k − 2 15: return k 25 Algorithm 5 Quy trình Apply-R2(L, k, i, j, g) 1: if L[k − 3].l < L[k − 1].l then 2: L[k − 1].l← L[k − 1].l − L[k − 3].l 3: L[k − 4].l← L[k − 4].l + L[k − 2].l 4: L[k − 2]← L[k] 5: L[k − 3]← L[k − 1] 6: k ← k − 2 7: else 8: l′ ← L[k − 3].l − L[k − 1], l”← L[k].l 9: d← L[k].d 10: while l′ ≥ L[k − 3].l − L[k − 1].l hoặc l” ≥ L[k − 2].l do 11: ← Next-Vertex (S, i, j, d, g) 12: if d = dk−3 then l′ ← l′ + l 13: else 14: if d = dk−1 then l′ ← l′ − l 15: else 16: if d = dk then l”← l” + l 17: else 18: if d = dk−2 then l”← l”− l 19: if d = dk−2 then 20: L[k − 2].l← L[k − 2].l − l” 21: L[k − 3].l← l′ 22: k ← k − 2 23: else 24: if d = dk−1 then 25: L[k − 3].l← L[k − 3].l − L[k − 1].l 26: L[k − 2].l← L[k − 2].l − l” 27: L[k − 1].l← L[k − 3].l − L[k − 1].l − l′ 28: k ← k − 1 29: return 26 theo hướng đi của đỉnh đó. Nếu hướng đi này giống hướng đi của L[k− 3] thì l′ được cập nhật thành l′ + l; nếu hướng đi này giống hướng đi của L[k− 1] thì l′ được cập nhật thành l′ − l (Bước 13-15). Tương tự l” cũng được sửa đổi (Bước 16-19). Do đó, mỗi lần đỉnh mới được truy cập, tham số l′ và l” cũng được sửa đổi. Khi thoát khỏi vòng lặp While, hai quy tắc R22 và R23 được áp dụng tùy theo hướng di chuyển của đỉnh hiện tại. Nếu hướng di chuyển này giống hướng của từ L[k − 2] (Bước 20), thì R22 được áp dụng (Bước 20-23). Nếu hướng đi này giống hướng đi từ L[k − 1], thì R23 được áp dụng (Bước 24-29). Giá trị của k được điều chỉnh lại thành k − 2 (Bước 23) cho quy tắc R22 và cho k − 1 (Bước 29) cho quy tắc R23. Quy trình trả về k và (Bước 30). Mệnh đề 2.2.1. [9] Cho đa giác lưới S nằm trong lướiG có cỡ g. Khi đó, thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya cho chúng ta chính xác bao lồi trực giao của S trên lưới G. Chứng minh. Thuật toán là chính xác vì bao lồi trực giao được tạo ra bởi thuật toán Otho-Hull tuân thủ tính lồi trực giao qua mỗi bước đồng thời bao lồi trực giao tạo ra bởi thuật toán có diện tích tối thiểu. Thật vậy, chúng ta thấy rằng, nếu p nằm trên một đường lưới và nằm bên trái đa giác lưới S, thì 0 < dT (p, S) = h ≤ g (ở đó dT (p, q) = max{|ip−iq|, |jp−jq|} là kí hiệu của khoảng cách trực giao giữa hai điểm p(ip, jp) và q(iq, jq); dT (p, S) = min{dT (p, q), q ∈ S}). Vì khi h > g thì trong bốn ô Q1, . . . , Q4 không có ô nào nằm trong đa giác lưới S. Khi đó, mỗi ô nằm bên trái đường đi xung quanh đa giác lưới S và mỗi ô tự do (bốn ô liền kề đều không nằm trong đa giác lưới S) nằm bên phải đường đi. Các ô tự do nằm trong bao lồi trực giao khi và chỉ khi các quy tắc loại bỏ vùng lõm được áp dụng. Rõ ràng, từ các quy tắc Mục 2.1 thì số lượng các ô tự do trong bao lồi trực giao là tối thiểu. Để chỉ ra rằng, giao điểm của bao lồi trực giao với bất kì đường nằm ngang hoặc đường thẳng đứng (đường lưới hoặc không là đường lưới) nào đều là rỗng hoặc là duy nhất một đoạn thẳng, chúng ta chỉ cần quan sát đa giác cuối cùng không chứa hai đỉnh loại 3 liên tiếp. Theo các quy tắc loại bỏ vùng lõm (ngoại trừ quy tắc R21 và quy tắc R23), kết quả của mỗi quy tắc không chứa hai đỉnh 27 loại 3 liên tiếp. Kết quả của R21 hoặc R23 có mẫu 33 ở cuối được loại bỏ tùy thuộc vào đỉnh tiếp theo. Trong lần lặp lại cuối cùng, đỉnh cuối cùng được truy cập trùng với đỉnh bắt đầu. Đỉnh này thuộc loại 1 và do đó một trong các quy tắc R11, R12, R13 được áp dụng. Khi kết thúc thuật toán chúng ta không có hai đỉnh loại 3 liên tiếp. Mệnh đề 2.2.2. [9] Thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya có độ phức tạp thời gian là O(n) với n là số đỉnh của đa giác lưới S. Chứng minh. Do xuất phát từ một đa giác lưới, nên một ô bất kì nằm trong đa giác lưới S có đỉnh là điểm lưới q được xác định bởi giao điểm của đa giác lưới và bốn cạnh tương ứng của ô đó. Đối với mỗi cạnh, giao điểm có thể kiểm tra trong thời gian O(g). Do đó, để kiểm tra một ô bất kì có nằm trong đa giác lưới hay không cần thời gian 4×O(g) = O(g). Trong quá trình di chuyển của các điểm lưới nằm trên biên đa giác lưới, chúng ta truy cập từng điểm qi từ điểm qi−1 bằng cách sử dụng thông tin về giao điểm của đa giác lưới và các cạnh tại qi−1. Ví dụ, Hình 2.1 (a), nếu qi−1 là loại đỉnh thuộc loại 1 và đã được truy cập hướng di−1 (hướng từ trên xuống) (đã biết trước đó thông qua đỉnh qi−2), thì qi được truy cập từ cạnh nằm ngang của qi−1. Do đó số lượng điểm lưới được truy cập trong khi di chuyển trực giao theo đường biên của đa giác lưới được giới hạn bởi O(n/g), ở đó n là số đỉnh của đa giác lưới S. Chú ý rằng, với một đa giác lưới, n là số cố định. Do đó độ phức tạp để truy cập tất cả các đỉnh là O(n/g).O(g) = O(n). Chúng ta thấy, mỗi đỉnh trên đường biên của đa giác lưới được truy cập một lần (Hình 2.1 (a),(b),(d)) hoặc hai lần (Hình 2.1 (c)). Thời gian dùng để phát hiện và loại bỏ mẫu chứa hai đỉnh loại 3 liên tiếp (gồm các loại của bốn đỉnh cuối cùng trong danh sách L) mất thời gian O(1) và sử dụng quy tắc loại bỏ vùng lõm nếu cần thiết. Nếu loại của hai đỉnh cuối cùng trong danh sách L không chứa hai đỉnh loại 3 liên tiếp thì thời gian cần để truy cập một đỉnh mới là O(1). Nếu loại của hai đỉnh cuối cùng trong danh sách L có dạng là 33 thì cần thời gian O(1) để áp dụng quy tắc loại bỏ vùng lõm nếu cần thiết. Số lần giảm tối đa được giới hạn bởi O(n/g)− 4 vì nhiều nhất O(n/g) đỉnh được cập nhật và 28 bao lồi trực giao ít nhất là bốn đỉnh. Do đó, tổng số hoạt động được giới hạn bởi (O(n/g)− 4).O(1) = O(n/g). Như vậy, tổng thời gian để tìm bao lồi trực giao của một đa giác lưới là O(n) +O(n/g) = O(n). Lưu ý rằng, ở đây giá trị của g có thể thay đổi và giá trị nhỏ nhất của g là 1. 2.3 VÍ DỤ MINH HỌA Hình 2.9: Bao lồi trực giao (đường nét liền đậm) của một đa giác lưới có đường viền là nét liền nhạt Một