Tài liệu SỬ DỤNG KỸ THUẬT “PHỄU” VÀ “CÂY PHỄU” ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Mỹ Hạnh SỬ DỤNG KỸ THUẬT “PHỄU” VÀ “CÂY PHỄU” ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2020 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Mỹ Hạnh SỬ DỤNG KỸ THUẬT “PHỄU” VÀ “CÂY PHỄU” ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN Chuyên ngành: Toán ứng dụng Mã số: 8460112 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 - 2020 LỜI CAM ĐOAN Tôi xin cam đoan mọi kết quả của đề tài: Sử dụng kỹ thuật “phễu” và “cây phễu” để tìm đường đi ngắn nhất trên bề mặt của khối đa diện đã được trình bày trong ba bài báo [7], [10] và [5], các ví dụ và số liệu trong luận văn là trung thực. Nếu không đúng như đã nêu trên, tôi xin hoàn toàn chịu trách nhiệm về đề tài của mình. Hà Nội, ngày 25 tháng 8 năm 2020 Nguyễn Thị Mỹ Hạnh LỜI CẢM ƠN Lời đầu tiên trong bản luận văn tôi xin gửi lời cảm ơn chân thành tới PGS. TS. Phan Thành An đã hướng dẫn tôi hoàn thiện bản luận văn này. Mặc dù rất bận rộn với công việc nhưng thầy vẫn luôn dành những thời gian quý giá của mình để hướng dẫn và chỉ bảo tôi tận tình. Trong quá trình làm luận văn bản thân tôi còn có nhiều thiếu sót, tuy nhiên thầy đã luôn luôn động viên và tạo điều kiện tốt nhất để tôi có thể hoàn thiện bản luận văn của mình. Tôi xin bày tỏ lòng biết ơn sâu sắc tới toàn thể các thầy cô trong Viện Toán học đã truyền đạt, chia sẻ cho tôi những kiến thức bổ ích. Đồng thời, tôi cũng xin bày tỏ sự biết ơn sâu sắc tới các thầy cô và các anh chị em của Học viện Khoa học và Công nghệ đã giúp đỡ và quan tâm tôi trong suốt quá trình học tập. Tôi cũng xin được gửi lời cảm ơn tới gia đình, bạn bè và anh chị trong nhóm nghiên cứu đã luôn cổ vũ, động viên, giúp đỡ tôi trong quá trình tham gia nhóm nghiên cứu để tôi củng cố được kiến thức và trau dồi các kĩ năng sử dụng các phần mềm hỗ trợ cho đề tài của mình. Hà Nội, ngày 25 tháng 8 năm 2020 Nguyễn Thị Mỹ Hạnh Mục lục LỜI CAM ĐOAN 3 LỜI CẢM ƠN 0 DANH MỤC KÍ HIỆU 3 MỞ ĐẦU 4 1 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN 6 1.1 ĐA GIÁC ĐƠN . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 ĐỒ THỊ, CÂY VÀ CHU TRÌNH, CÂY ĐỐI NGẪU . . . . 8 1.3 HÌNH ỐNG TAY VÀ HÌNH “PHỄU” . . . . . . . . . . . . . 11 1.4 THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN . . . . . . . . . . . . . . . 14 2 TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN 19 2.1 PHÉP LẬT . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 THUẬT TOÁN DÙNG NGUỒN SÁNG VÀ BÓNG . . . . . 23 3 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG MỘT DÃY MẶT TAM GIÁC TRONG KHÔNG GIAN BA CHIỀU 31 3.1 ĐƯỜNG TRẮC ĐỊA THẲNG NHẤT VÀ CÁC PHỄU DỌC THEO DÃY MẶT TAM GIÁC TRONG KHÔNG GIAN BA CHIỀU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1 2 3.2 3.3 THUẬT TOÁN TÌM CHÍNH XÁC ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM DỌC THEO DÃY MẶT TAM GIÁC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 ỨNG DỤNG THUẬT TOÁN NFU TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ MỘT ĐIỂM TỚI TẤT CẢ CÁC ĐIỂM TRÊN BỀ MẶT KHỐI ĐA DIỆN . . . . . . . . . . . . . . . . . . 43 KẾT LUẬN 51 TÀI LIỆU THAM KHẢO 52 3 DANH MỤC KÍ HIỆU [a, b] Một đoạn thẳng giới hạn bởi hai điểm a và b E = (e1 , . . . , em ) Một dãy các cạnh chung F = (f1 , . . . , fm+1 ) Một dãy mặt có m + 1 tam giác liền kề Fpq (s) Một phễu dọc theo F tương ứng với [p, q] có chóp là điểm s G Một đồ thị vô hướng P = (q1 , q2 , . . . , qn ) Một đa giác đơn có n đỉnh di Một đường chéo của đa giác P vi (1) ; vi (2) SP (s, vi (j) Hai điểm đầu mút của đường chéo di ) Đường đi ngắn nhất từ s tới điểm cuối vi (j) Ri Phễu được giới hạn bởi SP (v, vi (1) ), SP (v, vi (2) ) và đường chéo di I ei Ảnh của của điểm nguồn s lên cạnh ei Ie P rojei i Hình chiếu của Iei lên cạnh ei CF (u, v) Đường trắc địa thẳng nhất từ u tới v 4 MỞ ĐẦU Hiện nay, một trong những vấn đề đang được các nhà khoa học nghiên cứu trong lĩnh vực tối ưu, hình học tính toán là tính được đường đi ngắn nhất giữa hai điểm trên bề mặt của một khối đa diện, điều này rất có ích trong ngành công nghiệp chế tạo rô-bốt, tối ưu hệ thống thông tin địa lý và điều hướng (xem [1, 2, 3, 4]). Để giải quyết bài toán nói trên, nhiều nhà khoa học đã đưa ra các phương án cho việc tìm đường đi ngắn nhất giữa hai điểm trong một dãy mặt tam giác trên bề mặt của khối đa diện (xem [5, 6]). Năm 1984, Lee và Preparata [7] đã giới thiệu một thuật toán để tìm đường đi ngắn nhất giữa hai điểm trong một đa giác đơn với độ phức tạp thời gian là O(n log n) với n là số đỉnh của đa giác đơn. Năm 1986, Sharir and Schorr [8] đã trình bày một thuật toán tìm đường đi ngắn nhất giữa hai điểm trên bề mặt của khối đa diện lồi với n đỉnh của một khối đa diện cùng độ phức tạp thời gian là O(n3 log n). Thuật toán này cũng được cải tiến hơn với độ phức tạp thời gian là O(n2 log n) bởi Mount vào năm 1987 [9]. Với bài toán tìm các đường đi ngắn nhất từ một điểm cố định tới các đỉnh còn lại trên bề mặt của khối đa diện, khối đa diện ở đây không nhất thiết phải lồi, năm 1990, Chen and Han công bố một thuật toán với độ phức tạp thời gian là O(n2 ) [10] với n là số mặt của khối đa diện đang xét. Tuy nhiên, điểm yếu của thuật toán mà Chen và Han đưa ra là phải lật các mặt tam giác của một dãy mặt tam giác liền kề và sắp xếp chúng lại theo thứ tự. Năm 2019, An đã sử dụng kĩ thuật lật phẳng cùng với ý tưởng "Phễu" dọc theo dãy mặt tam giác để tính toán đường đi ngắn nhất giữa hai điểm cùng với độ phức tạp thời gian là O(n2 ) với n là số mặt của dãy tam giác đang xét. 5 Luận văn trình bày lại một số thuật toán về tìm đường đi ngắn nhất trong một đa giác đơn, một khối đa diện và một dãy mặt tam giác trong không gian ba chiều theo ba chương. Chương 1: Tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn. Chương đầu tiên, luận văn trình bày lại một số khái niệm về lý thuyết đồ thị, giới thiệu khái niệm về đa giác đơn, cây đối ngẫu để từ đó hình thành khái niệm về hình ống tay, hình phễu. Bên cạnh đó, luận văn cũng trình bày thuật toán tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn của Lee và Preparata (hay còn gọi là thuật toán "Phễu") năm 1984 [7] và đưa ra một ví dụ minh hoạ cho thuật toán. Chương 2: Tìm đường đi ngắn nhất trên bề mặt khối đa diện. Trong chương này, luận văn trình bày lại khái niệm về phép lật dãy mặt tam giác lên cùng một mặt phẳng, định nghĩa về hình chiếu của ảnh nguồn lên một cạnh, bóng của hình chiếu và thuật toán về "tìm đường đi ngắn nhất từ một điểm nguồn tới tất cả các đỉnh còn lại trên bề mặt khối đa diện" bằng việc sử dụng nguồn sáng và bóng. Thuật toán này được trình bày trong [10] năm 1990. Chương 3: Tìm đường đi ngắn nhất giữa hai điểm trong dãy mặt tam giác trong không gian ba chiều. Ở chương cuối cùng, luận văn trình bày thuật toán “Tìm đường đi ngắn nhất giữa hai điểm trong dãy mặt tam giác trong không gian ba chiều” được đưa ra bởi An năm 2019 [5] bằng việc sử dụng ý tưởng “phễu” và kĩ thuật lật phẳng. Luận văn trình bày lại khái niệm đường trắc địa thẳng nhất, khái niệm “phễu” và việc xác định "phễu" mới qua phép lật phẳng. Bên cạnh đó, luận văn chứng minh được rằng ảnh của các “phễu” sau khi lật không bị đè lên nhau. Phần cuối cùng, luận văn sẽ trình bày về việc ứng dụng thuật toán “tìm đường đi ngắn nhất giữa hai điểm dọc theo dãy mặt tam giác trong không gian ba chiều” để giải bài toán “tìm đường đi ngắn nhất trên bề mặt khối đa diện”. 6 Chương 1 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN Trong chương này, luận văn trình bày lại một số kiến thức cơ bản trong lý thuyết đồ thị, các khái niệm về đa giác đơn, cây đối ngẫu, hình ống tay và “Phễu” trong không gian hai chiều được trình bày và là nền tảng để xây dựng thuật toán tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn có sử dụng kĩ thuật “Phễu”. 1.1 ĐA GIÁC ĐƠN Để giải quyết được bài toán về tìm đường đi ngắn nhất giữa hai điểm s và t nằm trong đa giác đơn mà đường đi ngắn nhất đó không cắt biên của đa giác, chúng tôi sẽ trình bày lại một vài định nghĩa sau: Hình 1.1 Một đường gấp khúc đơn. 7 Định nghĩa 1.1.1. [7] Một đường gấp khúc đơn là một dãy các điểm qi (i = 1, 2, . . . , k ), ở đó tất cả các cặp điểm liền kề như qi và qi+1 được nối thành một đoạn (i = 1, 2, . . . , k − 1) và không có hai đoạn không liên tiếp nào cắt nhau (xem hình 1.1). Khi chuỗi đường gấp khúc đơn là một vòng tròn khép kín sẽ xác định được một đa giác. Định nghĩa 1.1.2. [7] Một đa giác đơn có n đỉnh P = (q1 , q2 , . . . , qn ) là một chuỗi đa giác với qn+1 = q1 , tức là qn được nối với q1 . Một đường chéo của P là một đoạn [qi , qj ], j 6= i + 1 và không cắt bất kì một cạnh nào của P . P được tam giác phân nếu miền trong của nó được chia ra bởi n − 2 tam giác và n − 3 đường chéo. Hình 1.2 Hình 1.3 Một đa giác đơn P = (q1 , q2 , q3 , q4 , q5 , q6 ). Đa giác đơn P được tam giác phân bởi các đường chéo [q1 , q3 ], [q3 , q6 ], [q6 , q4 ]. Chúng ta thấy trên hình 1.3 là một đa giác đơn 6 đỉnh đã được tam giác phân thành 4 tam giác bởi 3 đường chéo. 8 1.2 ĐỒ THỊ, CÂY VÀ CHU TRÌNH, CÂY ĐỐI NGẪU Các khái niệm sau đây sẽ là kiến thức cơ sở cho bài toán về tìm đường đi ngắn nhất trong một đa giác đơn hoặc một khối đa diện. Ở đây, luận văn chỉ trình bày các khái niệm liên quan đến đồ thị vô hướng. Hình 1.4 Minh hoạ một đồ thị vô hướng. Định nghĩa 1.2.1. [15] Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), trong đó V là một tập khác rỗng gồm các đỉnh, E là một tập gồm các cạnh - mỗi cạnh có hai đầu mút tạo bởi hai đỉnh của đồ thị vô hướng G. Khi biểu diễn một đồ thị vô hướng trên mặt phẳng ta biểu diễn các đỉnh của đồ thị bởi các đường tròn nhỏ, các cạnh còn lại được biểu diễn bằng một đường cong nối các đỉnh của cạnh. Ta kí hiệu một cạnh e được giới hạn bởi hai đầu mút là hai đỉnh a và b là e = [a, b], khi đó a và b được gọi là hai đỉnh kề nhau, hai cạnh có chung một đỉnh được gọi là hai cạnh kề nhau. Cung dạng [b, b] với b ∈ V được gọi là khuyên (xem Hình 1.4). Bậc của v là số các đỉnh kề với v . Ví dụ 1.2.1. Cho đồ thị G = (V, E) với V = {a, b, c, d, e} và E = {[a, b], [b, b], [b, c], [c, d], [d, e], [e, c]}. Khi đó G là một đồ thị vô hướng được biểu diễn như Hình 1.4. 9 Định nghĩa 1.2.2. [15] Với G = (V, E) là một đồ thị vô hướng, một hành trình được định nghĩa trong G là một dãy v0 e1 v1 e2 . . . en vn sao cho với mọi i = 0, 1, 2, . . . , n, vi ∈ V và i = 1, 2, . . . , n, ei là cạnh kề của các đỉnh vi−1 và vi . Khi đó, n được gọi là độ dài, v0 được gọi là đỉnh đầu, vn được gọi là đỉnh cuối. Ta nói rằng, một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Một hành trình được gọi là đường nếu các đỉnh của hành trình đó đều khác nhau. Một hành trình khép kín được gọi là chu trình nếu nó có độ dài ít nhất là 3 và khi xoá đi một đỉnh cuối thì trở thành đường. Định nghĩa 1.2.3. [15] Một đồ thị G = (V, E) được gọi là liên thông nếu hai đỉnh vi và vj khác nhau bất kì của G tồn tại một hành trình vô hướng trong G với đỉnh đầu là vi và đỉnh cuối là vj . Định nghĩa 1.2.4. [15] Một đồ thị vô hướng liên thông không có khuyên, không có chu trình được gọi là cây. Hình 1.5 Minh hoạ một cây. Coi một đa giác đơn P đã được tam giác phân giống như một không gian đồ thị G mà ở đó mỗi mặt của tam giác sẽ tương ứng với một nút điểm của đồ thị và mỗi cạnh sẽ được tạo thành bởi việc nối hai nút điểm với nhau. Khi đó, đồ thị đối ngẫu sẽ trở thành một cây mà các đỉnh của nó có bậc lớn nhất là 3. 10 Định nghĩa 1.2.5. [7] Cây đối ngẫu của một đa giác đơn P đã được tam giác phân là một đồ thị G = (V, E) sao cho mỗi nút của V tương ứng với một tam giác thuộc đa giác đơn P và mỗi cạnh của E nối hai nút thuộc V của hai tam giác có chung một đường chéo trong P. Ví dụ 1.2.2. Xét một đa giác đơn P = (q1 , q2 , . . . , q11 ) được tam giác phân bởi các đường chéo [q2 , q3 ], [q2 , q4 ], [q4 , q5 ],[q5 , q6 ], [q6 , q7 ], [q7 , q8 ], [q8 , q9 ], [q6 , q8 ]. Xác định một cây đối ngẫu của đa giác đơn P . Hình 1.6 Đa giác đơn được P được tam giác phân bởi các đường chéo. Hình 1.7 Cây đối ngẫu là đường màu đỏ của đa giác đơn P . Kí hiệu 4(s) là tam giác chứa điểm s và 4(t) là tam giác chứa điểm t, đường đi ngắn nhất từ điểm s tới t trong đa giác đơn P là π . Vì G = (V, E) là một cây nên trong G sẽ tồn tại duy nhất một đường đi nối hai đỉnh của V tương ứng với 4(s) và 4(t) (hai đỉnh này có thể không trùng với s và t). Hơn nữa, mỗi cạnh thuộc π lần lượt cắt mỗi đường chéo của P (theo thứ tự từ s đến t) tại một điểm duy nhất, và mỗi đường chéo của P chia P thành hai miền tương ứng chứa s và t. Vì thế đường đi ngắn nhất từ s tới t nằm trong P cũng sẽ cắt mỗi đường chéo 11 của P tại một điểm duy nhất. Hay nói một cách khác, đường đi ngắn nhất giữa hai điểm s và t cũng sẽ là một đường gấp khúc và bổ đề sau đây sẽ làm rõ hơn về điều này. Bổ đề 1.2.1. [7] Xét một đa giác đơn P có n đỉnh đã được tam giác phân bởi các đường chéo, ta kí hiệu là di (trong đó i = 1, . . . , n − 3). Cho S là tập hợp tất cả các điểm đầu mút của các đường chéo di (i = 1, . . . , n − 3) và đường đi ngắn nhất, khi đó tất cả các đỉnh của đường đi ngắn nhất giữa s và t sẽ nằm trong tập S ∪ {s, t}. Do S là tập hợp các điểm đầu và điểm cuối của các đường chéo nên ở đây S chính là tập hợp tất cả các đỉnh của đa giác đơn P . Vậy để tìm đường đi ngắn nhất giữa hai điểm s và t chúng ta sẽ cần phải tìm đường đi ngắn nhất từ s tới tất cả các điểm đầu mút của các đường chéo của P và điểm cuối cùng là điểm t. Hợp tất cả các đường đi ngắn nhất này sẽ tạo thành một cây G với gốc là điểm s. 1.3 HÌNH ỐNG TAY VÀ HÌNH “PHỄU” Để tìm các đỉnh của cây G = (V, E) không cần phải đi xét hết tất cả các đỉnh của đa giác đơn P mà chỉ cần tìm ra một miền thuộc đa giác đơn P cũng chứa đường đi ngắn nhất giữa hai điểm s và t. Để xác định được hình ống tay hay miền đa giác P cần xác định được miền chứa đường ngắn nhất từ s tới t. Định nghĩa 1.3.1. [7] Một đa giác đơn P đã được tam giác phân được gọi là hình ống tay nếu cây đối ngẫu của đa giác đơn P đó là một đường gấp khúc đơn. Chuyển bài toán tìm đường đi ngắn nhất giữa hai điểm của một đa giác đơn thành bài toán tìm đường đi ngắn nhất giữa hai điểm của một hình ống tay, việc tìm hình ống tay giúp giảm bớt việc xét các đỉnh thuộc đa giác đơn P mà đường ngắn nhất từ s tới t không đi qua, nhưng để giải quyết bài toán tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn thì Lee và Preparata đã đưa ra khái niệm về “phễu”. Xét một hình ống tay 12 Hình 1.8 Hình ống tay P 0 là miền được tô màu nâu. P có n đỉnh, s là điểm thuộc hình ống tay P , di là các đường chéo của P (1 ≤ n ≤ n − 3). Chúng ta sẽ kí hiệu: ˆ vi (1) và vi (2) là hai điểm đầu mút của đường chéo di (với 1 ≤ i ≤ n−3). ˆ SP (s, vi (j) ) là đường đi ngắn nhất từ s tới điểm cuối vi (j) với (j = 1, 2) nằm trong đa giác đơn P . Theo Bổ đề 1.2.1 thì tập tất cả các đỉnh mà đường SP (s, vi (j) ) đi qua với (j = 1, 2) đều là các đỉnh thuộc đa giác đơn P . ˆ Gọi v là điểm chung của SP (s, vi (1) ) và SP (s, vi (2) ) sao cho v là đỉnh xa nhất tính từ s. ˆ SPi = SP (s, vi (1) ) ∪ SP (s, vi (2) ). Hình 1.9 Hình ảnh minh hoạ cho hình phễu Ri với chóp phễu là v và cạnh chung di . 13 Định nghĩa 1.3.2. [7] Một miền Ri được giới hạn bởi SP (v, vi (1) ), SP (v, vi (2) ) và đường chéo di với (1 ≤ i ≤ n − 3) sẽ được gọi là “phễu”, v được gọi là chóp của phễu. Giả sử các đường gấp khúc con đề cập sau khác rỗng, khi đó SP (v, vi (j) ) với j = 1, 2 sẽ là một đường gấp khúc lồi hướng vào trong. Khi đó, chúng ta có mệnh đề sau. Mệnh đề 1.1. [7] Nếu SP (v, vi (j) ) là các đường gấp khúc lồi hướng vào trong thì cũng có nghĩa là mặt lồi của nó hướng vào miền trong của P . Chứng minh. Bằng phương pháp quy nạp, chúng ta sẽ chỉ ra được phễu Ri nằm hoàn toàn trong đa giác đơn P . Xét các đường chéo ds , ds+1 , . . . , di−1 bị cắt bởi các đường gấp khúc (1) (2) SP (v, vi (1) ) và SP (v, vi (2) ). Rõ ràng, 4vvs vs = Rs nằm hoàn toàn trong đa giác đơn P . Giả sử rằng Ri−1 ⊂ P , khi đó miền Ri mới được tạo thành từ miền Ri−1 hợp thêm với một phần hoặc toàn bộ một tam giác (tam giác chứa cạnh di ) nằm trong đa giác đơn P . Từ đó, chúng ta cũng suy ra được Ri ⊂ P . (j) Trong trường hợp SP (v, vi ) không là đường gấp khúc lồi trong thì theo bất đẳng thức tam giác (tổng của hai cạnh bao giờ cũng lớn hơn cạnh còn lại), ta luôn tìm được một đường đi ngắn nhất từ v tới vi và đường ngắn nhất đó luôn nằm trong đa giác đơn P . Điều này trái với giả thiết ban (j) đầu khi SP (v, vi ) là đường ngắn nhất từ v tới vi (xem Hình 1.10). (1) (2) Tính chất lồi này cũng chỉ ra rằng SP (v, vi ) và SP (v, vi ) bị chia nhánh nhiều nhất chỉ tại một đỉnh v , nếu chúng bị chia nhánh ở một đỉnh u1 nào đó thì nó sẽ lại gặp nhau tại một đỉnh u2 nào đó, và hai đường gấp khúc tách rời từ u1 tới u2 này phải là đường gấp khúc lồi trong. Khi đó, (1) (2) SPi = SP (v, vi ) ∪ SP (v, vi ), và v được gọi là đỉnh của hai đường gấp khúc lồi hướng trong. Ở đây, một trong hai đường gấp khúc có thể là rỗng (nhưng không (1) (2) (1) thể hai đường gấp khúc đó cùng rỗng, vì vi 6= vi ). Nếu SP (v, vi ) rỗng (2) thì rõ ràng SP (v, vi ) = di và ngược lại. Trong trường hợp này, phễu Ri suy biến không có miền trong và SPi trở thành một đường gấp khúc đơn. 14 Hình 1.10 (j) Hình ảnh minh hoạ cho tính lồi trong của SP (s, vi ). Để làm rõ được ý nghĩa của tính lồi trong, và một trong hai đường gấp khúc có thể rỗng, chúng ta sẽ cùng tìm hiểu kĩ hơn về thuật toán tìm đường đi ngắn nhất giữa hai điểm trong một đa giác đơn của Lee và Preparata trong phần dưới đây. 1.4 THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN Xuất phát từ một đỉnh nguồn s thuật toán sau đây xây dựng các (1) (2) đường SPi = SP (v, vi ) ∪ SP (v, vi ) chứa đường biên của phễu Ri cho (2) tới khi tới điểm đích (tức là vi ≡ t), chúng ta cùng đi xét bài toán sau: Bài toán: Xét một hình ống tay P và hai điểm cho trước s và t thuộc hình ống tay P đó. Tìm đường đi ngắn nhất từ s tới t nằm trong P . Hình 1.11 Hình ảnh minh hoạ cho bước tổng quát; hình a) uj ∈ ua ua−1 . . . u0 ; hình b) uj ∈ ua ua+1 . . . ub . 15 Algorithm 1 Thuật toán Lee và Preparata 1: 2: (1) (2) Bước khởi tạo: Xây dựng SP1 bằng cách nối s với v1 và v1 . Bước tổng quát: (Xây dựng SPi+1 từ SPi ) (1) (2) Xét v là đỉnh của SPi = SP (v, vi ) ∪ SP (v, vi ) SPi được chia làm hai nhánh tại v Chúng ta kí hiệu hai nhánh đó là ua ua+1 . . . ub và ua ua−1 . . . u0 (1) (2) Ở đó v = ua , vi = ub , vi = u0 Bắt đầu duyệt từ điểm u0 , u1 , . . . , ub (2) j là chỉ số nhỏ nhất sao cho vi+1 uj là đường tiếp tuyến của biên Ri . Chúng ta sẽ xét hai trường hợp: ˆ Trường hợp 1 : j ≤ a (xem Hình 1.11 a)) – Xoá hết các cạnh ul ul+1 với 0 ≤ l ≤ j − 1. (2) – Thêm cạnh uj vi+1 . ˆ Trường hợp 2 : j > a (xem Hình 1.11 b)) – Xoá hết các cạnh uj ul+1 với 0 ≤ l ≤ j − 1. (2) – Thêm cạnh uj vi+1 . – Miền Ri+1 sẽ nhận uj là đỉnh mới. 3: Bước kết thúc: Sau khi xây dựng được SPn−3 , đường chéo dn−2 chia P thành hai miền, và một trong hai miền này sẽ chứa điểm đích t. (2) - Gán vn−2 = t. (1) - Áp dụng bước tổng quát cho từng trường hợp với i = n−3 và SPn−2 = SP (s, vn−2 )∪SP (s, t). - SP (s, t) ⊂ SPn−2 . Ví dụ 1.4.1. Xét một đa giác đơn P với 13 đỉnh, một điểm nguồn s và điểm đích t (xem Hình 1.12). Tìm đường đi ngắn nhất từ s tới t bằng cách sử dụng thuật toán Lee và Preparata. Hình 1.12 Đa giác đơn P = (q1 , q2 , . . . , q13 ) có điểm nguồn là s và điểm tới là t. 16 Hình 1.13 Đa giác đơn P được tam giác phân bởi các đường chéo nét đứt. Hình 1.14 Hình 1.15 Hình 1.16 Cây đối ngẫu của đa giác đơn P là đường màu đỏ. Miền P 0 màu xanh lá là hình ống tay chứa đường đi ngắn nhất từ s tới t. Phễu thứ nhất giới hạn bởi SP (s, q11 ), SP (s, q13 ) và đường chéo [q11 , q13 ] có chóp là s.