CHƯƠNG 1 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Ố 1.1 TẬP LỒI VÀ BAO LỒI CỦA MỘT TẬP Định nghĩa 1. Một đoạn thẳng nối hai điểm (véc tơ) a và b trong Rn là tập hợp tất cả các điểm (véc tơ) x ∈ Rn có dạng {x ∈ Rn |x = (1 − λ)a + λb, 0 ≤ λ ≤ 1}. (xem [11]) Một tập S ⊆ Rn được gọi là một tập lồi nếu S chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó (Hình 1. Tức là S lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ (1 − λ)x + λy ∈ S Hình 1.2 lần lượt cho một ví dụ về tập lồi và tập không lồi.
Ta nói véc tơ x ∈ Rn gọi là tổ hợp lồi của các véc tơ x1 , x2 ,., xm ∈ Rn nếu m m i P P x= λi x , λi ≥ 0, ∀i = 1, 2, .1: Tập lồi Mệnh đề 1. (xem [11]) Một tập con S của Rn là tập lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là S lồi khi và chỉ khi: k k λj = 1, ∀x1 ,. Điều kiện đủ chúng ta suy ra từ định nghĩa tập lồi ứng với k = 2.
Bây giờ chúng ta sẽ chứng minh điều kiện cần của mệnh đề. Chúng ta sẽ chứng minh bằng quy nạp theo số điểm. Với k = 2, điều kiện cần chứng minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với k − 1 điểm, ta cần chứng minh mệnh đề đúng với k điểm.
Thật vậy, nếu x là tổ hợp lồi của k điểm x1 , x2 ,., xk ∈ S thì k k λj xj , λj ≥ 0, ∀j = 1, 2,. j=1 j=1 k−1 P Giả sử λk > 0, đặt ξ = λj. Khi đó, 0 < ξ < 1 và j=1 k−1 k−1 P λj λj xj + λk xk = ξ xj + λk xk. P x= j=1 j=1 ξ k−1 Pλ λj j Do = 1 và > 0 với mọi j = 1, 2, ., k − 1 nên theo giả thuyết quy j=1 ξ ξ nạp điểm 8 k−1 P λj y := xj ∈ S.
k P Do ξ > 0, λk > 0 và ξ + λk = λj = 1 nên x là một tổ hợp lồi của hai j=1 điểm y và xk đều thuộc S .2: Tập không lồi Mệnh đề 1. 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. 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 .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.
(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 9 lồi.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. 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. (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ó. (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 đó.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)).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 đó. Bao lồi trực giao của một tập là duy nhất. (xem [9]) Một lưới G 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. Mặt phẳng số là mặt phẳng được gắn thêm một lưới. (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.
(ii) Giao của OH(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 TRONG MẶ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.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: 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. 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.
(ii) Hai ô nằm trong đa giác lưới là chéo nhau. Khi đó, q là một đỉnh 270 (Hình 2. 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. 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 < ti , di , li >. 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 < j0 hoặc j = j0 và i > 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.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.