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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

16
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày lại một số kiến thức cơ sở bao gồm: định nghĩa về đường thẳng, đoạn thẳng, tập lồi, bao lồi của một tập, tập lồi trực giao và bao lồi trực giao của một tập; các tính chất liên quan của tập lồi, bao lồi, tập lồi trực giao và bao lồi trực giao.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Tìm bao lồi trực giao của một đa giác lưới trong mặt phẳng số

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Quyên TÌM BAO LỒI TRỰC GIAO CỦA MỘT ĐA GIÁC LƯỚI TRONG MẶT PHẲNG SỐ LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2019
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Quyên TÌM BAO LỒI TRỰC GIAO CỦA MỘT ĐA GIÁC LƯỚI TRONG MẶT PHẲNG SỐ Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Phan Thành An Hà Nội - 2019
LỜI CAM ĐOAN Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi, học hỏi của bản thân và sự hướng dẫn tận tình của thầy Phan Thành An. Mọi kết quả nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được trích dẫn cụ thể. Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kỳ một hội đồng bảo vệ luận văn thạc sĩ nào và cũng chưa hề được công bố trên bất kỳ một phương tiện nào. Tôi xin chịu trách nhiệm về những lời cam đoan trên. Hà Nội, ngày 1 tháng 4 năm 2019 Người cam đoan Nguyễn Thị Quyên
LỜI CẢM ƠN Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi đã hoàn thành luận văn tốt nghiệp thạc sĩ của mình. Để có được kết quả này tôi xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành đến thầy giáo của tôi, PGS. TS. Phan Thành An, người đã định hướng nghiên cứu cho tôi trong suốt quá trình thực hiện luận văn của mình. Cảm ơn thầy đã mang đến cho tôi những bài học quý báu về phương pháp nghiên cứu khoa học. Đó chính là nền tảng cơ bản, là những hành trang vô cùng quý giá để tôi có thể tiếp cận với khoa học thật sự. Thầy đã dạy cho tôi không chỉ những kiến thức khoa học mà còn cả những bài học về cuộc sống, về tình người. Xin cảm ơn thầy về tất cả những gì thầy đã mang đến cho tôi. Tôi xin gửi lời cảm ơn chân thành tới các thầy cô ở Viện Toán học đã luôn giúp đỡ tận tình, theo dõi và động viên tôi trong suốt quá trình thực hiện luận văn này. Xin cảm ơn những người thân trong gia đình đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và hoàn thành những công việc của mình. Xin cảm ơn chị Phong Thị Thu Huyền, tất cả những người thân yêu, những người đã yêu mến, chia sẻ với tôi những khó khăn vui buồn trong khi tôi thực hiện luận văn này. Nguyễn Thị Quyên
1 Mục lục DANH MỤC CÁC BẢNG . . . . . . . . . . . . . . . . . . . . . . . 2 DANH MỤC CÁC HÌNH VẼ . . . . . . . . . . . . . . . . . . . . . 3 MỞ ĐẦU 4 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Ố 6 1.1 TẬP LỒI VÀ BAO LỒI CỦA MỘT TẬP . . . . . . . . . . . . 6 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Ố . . . . . . . . . . . . . . . . 8 2 THUẬT TOÁN CỦA BISWAS, BHOWMICK, SARKAR VÀ BHAT- TACHARYA TÌM BAO LỒI TRỰC GIAO CỦA MỘT ĐA GIÁC LƯỚI TRONG MẶT PHẲNG SỐ 12 2.1 CÁC QUY TẮC . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 THUẬT TOÁN . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . . . . . . . . . . 28
2 DANH MỤC CÁC BẢNG Bảng 2.1 Bảng tính các đặc trưng của bốn chiếc máy bay từ bao lồi trực giao của chúng
3 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Tập lồi Hình 1.2 Tập không lồ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) Hình 1.4 Bao lồi trực giao của một số tập Hình 2.1 Các loại đỉnh khác nhau của một đa giác lưới 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) Hình 2.3 Quy tắc R11 cho mẫu 1331 Hình 2.4 Quy tắc R12 cho mẫu 1331 Hình 2.5 Quy tắc R13 cho mẫu 1331 Hình 2.6 Quy tắc R21 cho mẫu 1333 Hình 2.7 Quy tắc R22 cho mẫu 1333 Hình 2.8 Quy tắc R23 cho mẫu 1333 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 Hình 2.10 Minh họa thuật toán của A. Biswas, P. Bhowmick, M. Sarkar và B. B. Bhattacharya cho đa giác lưới trong Hình 2.9 Hình 2.11 Bao lồi trực giao (đường màu xanh nước biển) của Sukhoi Su-35 Hình 2.12 Bao lồi trực giao (đường màu xanh nước biển) của Lockheed Martin F-22 Raptor Hình 2.13 Bao lồi trực giao (đường màu xanh nước biển) của X1 Hình 2.14 Bao lồi trực giao (đường màu xanh nước biển) của X2
4 MỞ ĐẦU Tìm bao lồi là một trong những bài toán quan trọng trong lĩnh vực hình học tính toán bởi ứng dụng phong phú của nó. Một trong số những ứng dụng đó là nhận dạng mẫu, xử lý hình ảnh, tìm đường đi cho robot, số liệu thống kê, tìm tam giác phân Delaunay, tìm đường kính của một tập hợp, tìm các lớp lồi của một tập hợp,. . . Vì tầm quan trọng của nó nên nhiều nhà khoa học đã nghiên cứu và đưa ra thuật toán tìm bao lồi của một tập hợp. Vào năm 1970, D. R. Chand và S. S. Kapur lần đầu tiên xét bài toán này ([1]). Đến năm 1972, R. L. Graham đưa ra thuật toán quét Graham để giải bài toán ([2]). Một năm sau đó, R. A. Jarvis đưa ra thuật toán gói quà ([3]). Không lâu sau, W. Eddy năm 1977 ([4]) và A. Bykat năm 1978 ([5]) đưa ra thuật toán Quickhull, T. M. Chan năm 1996 với thuật toán Chan ([6]),. . . . Tuy nhiên, việc thực hiện các thuật toán kể trên cho một tập đủ lớn không nhanh như yêu cầu trong thực tế. Chẳng hạn, trong thuật toán Graham, muốn xác định điểm pi có rẽ trái, rẽ phải hay không rẽ, chúng ta cần xét điểm trước (pi−1 ) và sau nó (pi+1 ). Khi đó, ngoài việc sử dụng phép so sánh và cộng, trừ thì chúng ta còn sử dụng thêm phép nhân trong tính toán. Cũng như vậy, trong thuật toán gói quà, tọa độ cực của các điểm được tính từ tọa độ Descartes của chúng. Do đó, ngoài sử dụng phép so sánh và cộng, trừ thì thuật toán này còn sử dụng đến lượng giác. Hơn thế nữa, trong thực tế, tập lồi trực giao và bao lồi trực giao đã được nghiên cứu và ứng dụng đa dạng hóa trong nhiều lĩnh vực. Đặc biệt, trong lĩnh vực hình ảnh kĩ thuật số, bao lồi trực giao được sử dụng để khôi phục hình ảnh , che giấu lỗi trong các hình ảnh , . . . . Mặt khác, bao lồi trực giao còn được dùng để phân tích và phân loại hình dạng, trong lĩnh vực nhận dạng trong thời gian thực, . . . . Do đó việc tìm bao lồi trực giao của một tập là rất quan trọng. Vào năm 1982, D. Y. Montuno và A. Fournier đã xét bài toán tìm bao lồi trực giao của một tập đa giác trực giao ([7]). Sau đó, rất nhiều nhà khoa học đã đưa ra thuật toán để tìm bao lồi trực giao của một tập: năm 1983 có T. M. Nicholl, D.
5 T. Lee, Y. Z. Liao, và C. K. Wong ([8]); năm 2012 có A. Biswas, P. Bhowmick, M. Sarkar và B. B. Bhattacharya ([9]); năm 2005 có J. Wu và Z. Jiang ([10]). Đặc biệt, trong thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya ([9]) chỉ sử dụng phép so sánh và cộng, trừ các số nguyên nên chạy rất nhanh trong thời gian O(n) (ở đó n là số đỉnh của đa giác lưới đang xét, Chương 2, Mục 2.2). Với lý do trên, chúng tôi mong muốn nghiên cứu 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ố. Cụ thể, trong Chương 1, chúng tôi tìm hiểu về tập lồi, bao lồi của một tập, tập lồi trực giao, bao lồi trực giao của một tập. Trong Chương 2, chúng tôi trình bày lại các quy tắc để tìm bao lồi trực giao của một đa giác lưới, thuật toán tìm bao lồi trực giao của Biswas, Bhowmick, Sarkar và Bhattacharya ([9]), đưa ra ví dụ minh họa cụ thể cho thuật toán trên. Vì thời gian và kiến thức có hạn, nên luận văn không thể tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được những đóng góp quý báu từ phía bạn đọc.
6 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.1.1. (xem [11]) Một đường 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, λ ∈ R}. 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}. Định nghĩa 1.1.2. (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.1). Tức là S lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ (1 − λ)x + λy ∈ S Hình 1.1 và 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, ..., m, λi = 1. i=1 i=1
7 Hình 1.1: Tập lồi Mệnh đề 1.1.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 , ..., xk ∈ S ⇒ λj xj ∈ S . P P ∀k ∈ N, ∀λ1 , ..., λk ≥ 0 : j=1 j=1 Chứng minh. Đ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, ..., k, P P x= λj = 1. j=1 j=1 k−1 P Giả sử λk > 0, đặt ξ = λj . Khi đó, 0 < ξ < 1 và j=1 k−1 k−1 λj j λj xj + λk xk = ξ x + λk xk . P 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 j y := x ∈ S. j=1 ξ Ta có x = ξy + λk xk . 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 . 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
9 lồ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ướ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. Đị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ủ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. 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 < 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. 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