Luận văn Thạc sĩ Toán học: 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

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 8 1.2 ĐỒ THỊ, CÂY VÀ CHU TRÌNH, CÂY ĐỐI NGẪU . . . . 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 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

3.2 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

3.3 Ứ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

DANH MỤC KÍ HIỆU

Một đoạn thẳng giới hạn bởi hai điểm a và b

Một dãy các cạnh chung

Một phễu dọc theo F tương ứng với [p, q] có chóp là điểm s

Một đồ thị vô hướng

(2)

(j)

(j))

(1)), SP (v, vi

(2)) và đường chéo di

Iei ei

Một đường chéo của đa giác P 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 Phễu được giới hạn bởi SP (v, vi Ảnh của của điểm nguồn s lên cạnh ei Hình chiếu của Iei lên cạnh ei Đường trắc địa thẳng nhất từ u tới v

[a, b] E = (e1, . . . , em) F = (f1, . . . , fm+1) Một dãy mặt có m + 1 tam giác liền kề Fpq(s) G P = (q1, q2, . . . , qn) Một đa giác đơn có n đỉnh di (1); vi vi SP (s, vi Ri Iei P roj CF (u, v)

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.

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”.

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

Hình 1.1 Một đường gấp khú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:

Đị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.

Hình 1.2 Một đa giác đơn P = (q1, q2, q3, q4, q5, q6).

Hình 1.3 Đa giác đơn P được tam giác phân bởi các đường chéo [q1, q3], [q3, q6], [q6, q4].

Đị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 (cid:54)= 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.

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.

1.2 ĐỒ THỊ, CÂY VÀ CHU TRÌNH, CÂY ĐỐI NGẪU

Hình 1.4 Minh hoạ một đồ thị vô hướng.

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.

Đị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.

Đị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 v0e1v1e2 . . . envn 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.

Hình 1.5 Minh hoạ một cây.

Đị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.

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.

Đị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.

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 .

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 .

Kí hiệu (cid:52)(s) là tam giác chứa điểm s và (cid:52)(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 (cid:52)(s) và (cid:52)(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

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

Hình 1.8 Hình ống tay P (cid:48) 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:

(2) là hai điểm đầu mút của đường chéo di (với 1 ≤ i ≤ n−3).

(cid:136) vi (1) và vi (cid:136) 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à (j)) đi qua với (j = 1, 2) đều là các đỉnh thuộc đa giác đường SP (s, vi đơn P .

(2)) sao cho v là đỉnh

(cid:136) Gọi v là điểm chung của SP (s, vi

(1)) và SP (s, vi

(2)).

xa nhất tính từ s.

(cid:136) SPi = SP (s, vi

(1)) ∪ SP (s, vi

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.

(2))

(1)), SP (v, vi Định nghĩa 1.3.2. [7] Một miền Ri được giới hạn bởi SP (v, vi 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.

(j))

(j)) là các đường gấp khúc lồi hướng vào

Giả sử các đường gấp khúc con đề cập sau khác rỗng, khi đó SP (v, vi 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 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 .

(2)). Rõ ràng, (cid:52)vv(1)

s v(2)

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 .

(1)) và SP (v, vi

Xét các đường chéo ds, ds+1, . . . , di−1 bị cắt bởi các đường gấp khúc s = Rs nằm hoàn toàn

SP (v, vi 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 .

i ) 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 đầu khi SP (v, v(j)

i ) là đường ngắn nhất từ v tới vi (xem Hình 1.10).

Trong trường hợp SP (v, v(j)

i ) và SP (v, v(2)

i ) ∪ SP (v, v(2)

i ) 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 đó, SPi = SP (v, v(1) i ), và v được gọi là đỉnh của hai đường gấp khúc lồi hướng trong.

i ). Nếu SP (v, v(1)

Tính chất lồi này cũng chỉ ra rằng SP (v, v(1)

Ở đây, một trong hai đường gấp khúc có thể là rỗng (nhưng không (cid:54)= v(2) thể hai đường gấp khúc đó cùng rỗng, vì v(1) i ) rỗng thì rõ ràng SP (v, v(2) i ) = 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.

Hình 1.10 Hình ảnh minh hoạ cho tính lồi trong của SP (s, v(j)

Để 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

i ) ∪ SP (v, v(2)

đường SPi = SP (v, v(1) tới khi tới điểm đích (tức là v(2)

Xuất phát từ một đỉnh nguồn s thuật toán sau đây xây dựng các i ) chứa đường biên của phễu Ri cho i ≡ 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 1.11 Hình ảnh minh hoạ cho bước tổng quát; hình a) uj ∈ uaua−1 . . . u0; hình b) uj ∈

uaua+1 . . . ub.

hình ống tay P đó. Tìm đường đi ngắn nhất từ s tới t nằm trong P .

Algorithm 1 Thuật toán Lee và Preparata

1 và v(2) 1 .

1: Bước khởi tạo: Xây dựng SP1 bằng cách nối s với v(1) 2: Bước tổng quát: (Xây dựng SPi+1 từ SPi)

)

) ∪ SP (v, v(2)

i = ub, v(2)

i = u0

i+1uj là đường tiếp tuyến của biên Ri.

Xét v là đỉnh của SPi = SP (v, v(1) SPi được chia làm hai nhánh tại v Chúng ta kí hiệu hai nhánh đó là uaua+1 . . . ub và uaua−1 . . . u0 Ở đó v = ua, v(1) Bắt đầu duyệt từ điểm u0, u1, . . . , ub j là chỉ số nhỏ nhất sao cho v(2) Chúng ta sẽ xét hai trường hợp:

(cid:136) Trường hợp 1 : j ≤ a (xem Hình 1.11 a))

– Xoá hết các cạnh ulul+1 với 0 ≤ l ≤ j − 1.

– Thêm cạnh ujv(2) i+1.

(cid:136) Trường hợp 2 : j > a (xem Hình 1.11 b))

– Xoá hết các cạnh ujul+1 với 0 ≤ l ≤ j − 1.

– Thêm cạnh ujv(2) i+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.

- Gán v(2)

n−2 = t.

- Á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, v(1)

n−2)∪SP (s, t).

- SP (s, t) ⊂ SPn−2.

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.

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.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 Cây đối ngẫu của đa giác đơn P là đường màu đỏ.

Hình 1.15 Miền P (cid:48) màu xanh lá là hình ống tay chứa đường đi ngắn nhất từ s tới t.

Hình 1.16 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.

Hình 1.17 Phễu thứ hai giới hạn bởi SP (s, q11), SP (s, q3) và đường chéo [q3, q11] có chóp là s.

Hình 1.18 Phễu thứ ba giới hạn bởi SP (s, q11), SP (s, q4) và đường chéo [q4, q11] có chóp là s.

Hình 1.19 Phễu thứ tư giới hạn bởi SP (s, q10), SP (s, q4) và đường chéo [q4, q10] có chóp là s.

Hình 1.20 Phễu thứ năm giới hạn bởi SP (s, q4), SP (s, q9) và đường chéo [q4, q9] có chóp là s.

Hình 1.21 Phễu thứ sáu giới hạn bởi SP (s, q5), SP (s, q9) và đường chéo [q5, q9] có chóp là s.

Hình 1.22 Phễu thứ bảy bị suy biến, miền trong bằng rỗng, SP (s, q9) là đường màu hồng.

Hình 1.23 SP (s, t) = SP (s, q9) ∪ SP (q9, t) là đường đi ngắn nhất từ s tới t.

Chương 2

TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN

Trong chương này, luận văn trình bày thủ tục lật phẳng một dãy mặt tam giác theo các cạnh chung và việc xác định đường đi ngắn nhất từ một điểm nguồn s tới các đỉnh còn lại trên bề mặt của một khối đa diện mà các mặt đã được tam giác phân trong không gian ba chiều bằng cách sử dụng một thuật toán nguồn sáng và bóng [10]. Bên cạnh đó, luận văn cũng trình bày một ví dụ minh hoạ cho thuật toán.

2.1 PHÉP LẬT

Xét P là một mặt đa diện với các mặt đã được tam giác phân trong không gian ba chiều, với s là một đỉnh của khối đa diện P cần tìm ra một đường ngắn nhất từ điểm nguồn s tới các đỉnh còn lại trên bề mặt khối đa diện P . Luận văn sẽ trình bày lại một số khái niệm về dãy mặt, dãy cạnh mà Mitchell đưa ra năm 1987 [9].

F = (f1, f2, . . . , fm+1) và E = (e1, e2, · · · , em) lần lượt là một dãy các mặt và một dãy các cạnh, fi ∩ fi+1 = ei, f1 là tam tam giác chứa đỉnh nguồn s. Ngoại trừ các trường hợp cụ thể khác, các dãy mặt tam giác được đề cập đến sau đây đều dãy mặt mà các tam giác khác nhau từng đôi một. Kĩ thuật phép lật phẳng (planar unfolding) là phương pháp được sử dụng để tìm đường đi ngắn nhất. Ta thực hiện lật phẳng các mặt f1, f2, . . . , fm lần lượt theo e1, e2, . . . , em lên mặt phẳng chứa mặt fm+1.

Hình 2.1 Một dãy các mặt tam giác (f1, f2, . . . , fm+1) lần lượt liền kề theo các cạnh (e1, e2, · · · , em).

Thủ tục lật phẳng

1: F = {f1}. 2: For i:=1 to m do

Quay F quanh ei cho tới khi F và fi+1 cùng nằm trên một mặt phẳng và khác phía với mặt

fi+1 so với cạnh ei;

F := F ∪ {ei, fi+1}.

3: End

Quy trình này dừng lại khi các mặt f1, f2, . . . , fm cùng nằm trên mặt phẳng chứa mặt fm+1.

Thủ tục của phép lật dãy mặt F được mô tả như sau [10]:

Ưu điểm của phép lật khi sử dụng để giải bài toán tìm đường đi ngắn nhất là giúp chúng ta đưa bài toán từ không gian ba chiều về bài toán trong không gian hai chiều mà không mất đi độ chính xác về khoảng cách giữa hai điểm trên một mặt và độ lớn các góc trong cùng một mặt phẳng.

Bổ đề 2.1.1. Với một dãy mặt F = (f1, f2, · · · , fm+1) và dãy cạnh chung E = (e1, e2, · · · , em) khi thực hiện phép lật phẳng các mặt f1, f2, . . . , fm lên mặt phẳng chứa mặt phẳng fm+1 thì độ lớn của các góc trong một mặt tam giác fi và khoảng cách hai điểm p và q (với p, q ∈ fi, 1 ≤ i ≤ m + 1) được bảo toàn.

Ví dụ 2.1.1. Xét dãy mặt tam giác F = {(cid:52)v0v1v2, (cid:52)v1v2v3, (cid:52)v1v3v4} và dãy cạnh E = {[v1, v2], [v1, v3]} như hình 2.2, các đỉnh v0(0, 0, 3), v1(0, 0, 0), v2(0, −3, 0), v3(3, 0, 0), v4(0, 0, −3). Thực hiện lật mặt phẳng mặt (cid:52)v0v1v2 và (cid:52)v1v2v3 lên mặt phẳng chứa (cid:52)v1v3v4 lần lượt theo dãy cạnh {[v1, v2], [v1, v3]}.

Hình 2.2 Minh hoạ dãy mặt tam giác {(cid:52)v0v1v2, (cid:52)v1v2v3, (cid:52)v1v3v4 }.

Ta thực hiện theo đúng quy trình phép lật phẳng dãy mặt tam giác:

(cid:136) Bước 1: Ta chọn F := {(cid:52)v0v1v2}, quay F quanh cạnh [v1, v2] tới khi mặt (cid:52)v0v1v2 và mặt (cid:52)v1v2v3 cùng nằm trên một mặt phẳng và hai mặt phẳng này nằm khác phía so với cạnh v1v2. Khi đó, F := F ∪ {[v1, v2], (cid:52)v1v2v3}. Nhận thấy rằng hai mặt (cid:52)v0v1v2, (cid:52)v1v2v3 tạo với nhau một góc ψ = 90o, khi thực hiện quay mặt chứa F lên mặt phẳng chứa (cid:52)v1v2v3 bằng ma trận quay [14] ta có thể tính được toạ độ của I[v1,v2](x(cid:48), y(cid:48), z(cid:48)) - là ảnh của của v0 sau khi lật ứng với cạnh [v1, v2], x(cid:48), y(cid:48), z(cid:48) lần lượt là toạ độ của I[v1,v2] theo các trục Ox, Oy, Oz. Ta có

    

0

    =        0 0   . 3 1

cos φ 0 sin φ 0 0 1 − sin φ 0 cos φ 1 1 0

0 x(cid:48) y(cid:48) z(cid:48) 1

Hình 2.3 Minh hoạ phép lật mặt phẳng (cid:52)v0v1v2 lên mặt phẳng chứa (cid:52)v1v2v3 qua cạnh [v1, v2].

Mặt khác khi lật chúng ta cần mặt chứa (cid:52)v3v0v1 nằm ở mặt còn lại của cạnh v1v2 nên φ = −(180o − ψ).

   

  .   =      0 0  3  1  0 0 −1 0 0 0 1  0 1 0  1 0 0

0 0 0

x(cid:48) y(cid:48) z(cid:48) 1

Vậy toạ độ của I[v1v2] là (−3, 0, 0).

(cid:136) Bước 2: Với F := F ∪ {[v1, v2], (cid:52)v1v2v3}, quay F quanh cạnh [v2, v3] tới khi F và mặt (cid:52)v2v3v4 cùng nằm trên một mặt phẳng, F và mặt (cid:52)v2v3v4 nằm ở hai bên của cạnh [v2, v3]. Khi đó, F := F ∪ {[v2, v3], (cid:52)v2v3v4}. Nhận thấy rằng F và (cid:52)v2v3v4 tạo với nhau một góc ψ = 90o, khi thực hiện quay F lên mặt phẳng chứa (cid:52)v1v2v3 ta có thể tính được toạ độ của I[v2,v3](x(cid:48)(cid:48), y(cid:48)(cid:48), z(cid:48)(cid:48)) - là ảnh của của I[v1,v2] sau khi lật, x(cid:48)(cid:48), y(cid:48)(cid:48), z(cid:48)(cid:48) lần lượt là toạ độ của I[v2,v3] theo các trục Ox, Oy, Oz.

Hình 2.4 Minh hoạ dãy mặt tam giác {(cid:52)v0v1v2, (cid:52)v1v2v3, (cid:52)v1v3v4 }.

Ta có

    

0

  .     =    

−3 0 0 1

 1 0 0 cos φ − sin φ 0  cos φ 0 0 sin φ  1 0

0 x(cid:48)(cid:48) y(cid:48)(cid:48) z(cid:48)(cid:48) 1

Ở đây, φ = 90o.

    

0

  .       =  

−3 0 0 1

 1 0 0 0 0 −1 0  0 0 1  1 0 0

0 0

x(cid:48)(cid:48) y(cid:48)(cid:48) z(cid:48)(cid:48) 1

Vậy toạ độ của I[v2,v3] là (−3, 0, 0).

2.2 THUẬT TOÁN DÙNG NGUỒN SÁNG VÀ BÓNG

Thuật toán dùng nguồn sáng và bóng là một thuật toán xác định đường đi ngắn nhất từ một điểm nguồn tới các đỉnh còn lại trên bề mặt của khối đa diện. Thuật toán sử dụng kĩ thuật lật phẳng, lật tất cả các mặt f1, f2, . . . , fm lên mặt phẳng chứa mặt fm+1 lần lượt theo các cạnh chung ei. Kí hiệu fi là ảnh của fi với 1 ≤ i ≤ m, Iei là ảnh của của điểm nguồn s lên cạnh ei với 1 ≤ i ≤ m.

Iei ei

Hình 2.5 Hình chiếu của Iei lên cạnh ei.

Định nghĩa 2.2.1. [10] Hình chiếu của Iei lên cạnh ei là một đoạn thẳng nằm trên cạnh ei và được kí hiệu là P roj sao cho đường ngắn nhất từ Iei ei đi qua dãy các cạnh e1, e2, . . . , ei−1 điểm nguồn s tới điểm t với t ∈ P roj được lật thành một đoạn thẳng (hay chính là đường trắc địa). Điều này có Iei ei có thể nối Iei và t với nhau bằng một đoạn nghĩa là với bất kì t ∈ P roj thẳng chỉ đi qua dãy các cạnh e1, e1, . . . , ei−1 (xem Hình 2.5).

Tính chất sau về đường đi ngắn nhất [10]:

1. Một đường ngắn nhất đi qua một mặt không quá một lần.

2. Hai đường ngắn nhất không thể cắt nhau ngoại trừ tại hai điểm: điểm

Iei ei .

nguồn và điểm tới.

Iei−1 ei−1

Định nghĩa 2.2.2. [10] Nguồn sáng ứng với cạnh ei là tập hợp tất cả các đường đi ngắn nhất từ ảnh điểm nguồn s là Iei tới t với t ∈ P roj

trên mặt fi là miền Định nghĩa 2.2.3. [10] Bóng của hình chiếu P roj giới hạn bởi các đường đi ngắn nhất từ ảnh nguồn Iei tới cạnh ei và các hình chiếu của ảnh nguồn Iei lên các cạnh của mặt fi chứa nguồn sáng tương ứng với cạnh ei (xem Hình 2.6).

Hình 2.6 Bóng của hình chiếu P roj

trên mặt fi.

Iei−1 ei−1

Hình 2.7 Phân tích cạnh chung e về hai phía.

Phân tích một cạnh chung thành hai cạnh được định hướng sao cho ảnh nguồn chỉ có thể nằm phía bên trái của cạnh định hướng (xem Hình 2.7). Mặt nằm khác phía với cạnh định hướng được gọi là mặt bóng của cạnh định hướng đó, từ đó ta thấy được một mặt có thể là mặt bóng của ba cạnh của nó hay một mặt có thể có ba cạnh định hướng.

Thuật toán sau đây xây dựng một cây được gọi là cây tuần tự, một nút trong cây tuần tự này sẽ là một bộ ba và được kí hiệu là n = (e, I, P rojIe e ) với Ie là ảnh nguồn của e. Ta nói nút n nằm trên cạnh e, e là cạnh của n và bóng của n là bóng của P rojIe e .

Xuất phát từ một điểm nguồn s, tìm tất cả các đường đi ngắn nhất từ điểm nguồn s tới các đỉnh còn lại của khối đa diện P , chúng tôi đặt ra bài toán:

Algorithm 2 (Thuật toán Thơ ngây)

1: root:= s;

For tất cả các cạnh e đối diện với điểm nguồn s do thêm nút (e, s, e) là con của gốc s: /*e là cạnh của mặt có điểm nguồn s*/ /*s là một đỉnh của một mặt tam giác thuộc khối đa diện.*/

2: For i:= 1 to m do

For tất cả các lá (e, I, P rojI

/*m là số các mặt của khối đa diện sau khi các mặt đã được tam giác phân .*/ e ) tại mức ith do

Begin

lật I quanh cạnh e nhận được I: /* I cùng mặt phẳng với (cid:52)vpq,*/ /* mặt bóng của cạnh e.*/

For e(cid:48) := [v, p], [q, v]

tính P rojI e(cid:48); If P rojI

e(cid:48) khác rỗng then

thêm (e(cid:48), I, P rojI

e ).

e(cid:48)) là con của (e, I, P rojI

End.

Bài toán: Xét một khối đa diện P mà các mặt của khối đa diện đã được tam giác phân thành m mặt (xem Định nghĩa 1.1.2), (cid:52)vpq là một mặt của khối đa diện P . Tìm đường đi ngắn nhất từ một đỉnh nguồn s tới các đỉnh còn lại của khối đa diện đó.

Ví dụ 2.2.1. Xét một khối đa diện mà các mặt đã được tam giác phân thành 6 mặt (xem Hình 2.8) và các đỉnh s(0, 0, 3), v1(0, 0, 0), v2(3, 0, 0), v3(0, 3, 0), v4(1.5, 1.5, −3). Tìm đường đi ngắn nhất từ đỉnh nguồn S tới các đỉnh còn lại trên bề mặt của khối đa diện bằng cách sử dụng thuật toán 2.

Trong ví dụ này ta có thể chỉ ra được đường đi ngắn nhất trên bề mặt khối đa diện từ đỉnh S lần lượt tới các đỉnh v1 bằng 3, đường đi ngắn nhất từ s tới v2, v3 đều bằng 4.24, đường đi ngắn nhất trên bề mặt khối đa diện từ s tới v4 bằng 6.18.

Hình 2.8 Minh hoạ khối đa diện trong không gian ba chiều trong Ví dụ 2.2.

(cid:136) Bước 1: Ta gán: root:= s;

Các cạnh: [v1, v2], [v1, v3], [v2, v3] là các cạnh đối diện với gốc s. Khi đó: ([v1, v2], s, [v1, v2]), ([v1, v3], s, [v1, v3]), ([v2, v3], s, [v2, v3]) là con của gốc s.

(cid:136) Bước 2: Do khối đa diện này sau khi các mặt được tam giác phân sẽ

có tất cả 6 mặt nên cây chúng tôi xây dựng sẽ có 6 mức.

Mức 1: Đối với ([v1, v2], s, [v1, v2]), ([v1, v3], s, [v1, v3]), ([v2, v3], s, [v2, v3]) là lá ta thực hiện lật s lần lượt quanh các cạnh [v1, v2], [v1, v3], [v2, v3] lên mặt phẳng chứa các mặt (cid:52)v1v2v3, (cid:52)v3v4v6, (cid:52)v4v5v6, (cid:52)sv1v5 và ảnh của s tương ứng trên mỗi mặt phẳng lật là I[v1,v2], I[v1,v3], I[v2,v3].

– Đối với (cid:52)sv1v3 và (cid:52)v1v3v4 sau khi đồng phẳng, ta gán e(cid:48)

:= I[v1,v4] [v1,v4] của ảnh I[v3,v4] [v3,v4] của ảnh nguồn I[v3,v4]

[v1, v4], [v3, v4] và thực hiện tính hình chiếu P roj nguồn I[v1,v4] lên cạnh [v1, v4] và P roj lên cạnh [v3, v4].

(cid:16) (cid:17) (cid:16) (cid:17) Thêm và

[v1, v4], I[v1,v4], P roj

[v3, v4], I[v3,v4], P roj

I[v1,v4] [v1,v4]

I[v3,v4] [v3,v4]

là con của ([v1, v3], s, [v1, v3]). Nguồn sáng từ điểm nguồn s tới đỉnh v4 được tính bằng 6.18 và cắt cạnh [v1, v3] tại điểm có toạ độ là (0, 0.74, 0)

– Đối với (cid:52)sv1v2 và (cid:52)v1v2v4 sau khi đồng phẳng, ta gán e(cid:48)

:= I[v1,v4] [v1,v4] của ảnh I[v2,v4] [v2,v4] của ảnh nguồn I[v2,v4]

(cid:16) (cid:17) (cid:17)

[v1, v4], [v2, v4] và thực hiện tính hình chiếu P roj nguồn I[v1,v4] lên cạnh [v1, v4] và P roj lên cạnh [v2, v4]. (cid:16) Thêm

và

[v1, v4], I[v1,v4], P roj

[v2, v4], I[v2,v4], P roj

I[v1,v4] [v1,v4]

I[v2,v4] [v2,v4]

là con của ([v1, v2], S, [v1, v2]). Nguồn sáng từ điểm nguồn s tới đỉnh v4 được tính bằng 6.18 và cắt cạnh [v1, v2] tại điểm có toạ độ là (0.74, 0, 0)

– Đối với (cid:52)sv2v3 và (cid:52)v2v3v4 sau khi đồng phẳng, ta gán e(cid:48)

:= I[v2,v4] [v2,v4] của ảnh I[v3,v4] [v3,v4] của ảnh nguồn I[v3,v4]

(cid:17) (cid:16) (cid:17) và

[v2, v4], [v3, v4] và thực hiện tính hình chiếu P roj nguồn I[v2,v4] lên cạnh [v2, v4] và P roj lên cạnh [v3, v4]. (cid:16) Thêm

[v3, v4], I[v3,v4], P roj

[v2, v4], I[v2,v4], P roj

I[v3,v4] [v3,v4]

I[v2,v4] [v2,v4]

là con của ([v2, v3], S, [v2, v3]). Nguồn sáng từ điểm nguồn s tới đỉnh v4 được tính bằng 6.64 và cắt cạnh [v2, v3] tại điểm có toạ độ là (1.5, 1.5, 0)

Mức 2:

(cid:16) (cid:17) – Đối với lá

[v1, v4], I[v1,v4], P roj

I[v1,v4] ở mức 1 ta lại tiếp tục thực [v1,v4] hiện việc lật I[v1,v4] quanh cạnh [v1, v4] hoặc [v3, v4] để được ảnh nguồn mới tương ứng là I[v1,v4] và I[v3,v4]. (cid:16) Thêm

(cid:17) (cid:17) (cid:16)

[v1, v2], I[v1,v2], P roj

[v3, v4], I[v3,v4], P roj

I[v3,v4] [v3,v4]

I[v1,v2] [v1,v2] [v1, v4], I[v1,v4], P roj

(cid:16) (cid:17) và I[v1,v4] [v1,v4]

là con của . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v2 và bằng 6 và đi qua dãy cạnh [v1, v3], [v1, v2]. (cid:16) (cid:17) – Đối với lá

[v3, v4], I[v3,v4], P roj

I[v3,v4] ta lại tiếp tục thực hiện việc [v3,v4] lật I[v3,v4] quanh cạnh [v2, v3] hoặc [v2, v4] để được ảnh nguồn mới

(cid:17) (cid:16) (cid:16) (cid:17)

[v2, v4], I[v2,v4], P roj

I[v2,v4] [v2,v4]

I[v2,v3] [v2,v3] [v1, v4], I[v1,v4], P roj

tương ứng là I[v2,v3] và I[v2,v4]. [v2, v3], I[v2,v3], P roj Thêm (cid:16) (cid:17) và I[v1,v4] [v1,v4]

là con của . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v2 và bằng 6 và đi qua dãy cạnh [v1, v3], [v3, v4] (cid:16) (cid:17) – Đối với lá

[v1, v4], I[v1,v4], P roj

I[v1,v4] ở mức 1 ta lại tiếp tục thực [v1,v4] hiện việc lật I[v1,v4] quanh cạnh [v1, v3] hoặc [v3, v4] để được ảnh nguồn mới tương ứng là I[v1,v3] và I[v3,v4]. (cid:16) Thêm

(cid:16) (cid:17) (cid:17)

[v1, v3], I[v1,v3], P roj

[v3, v4], I[v3,v4], P roj

I[v3,v4] [v3,v4]

I[v1,v3] [v1,v3] [v1, v4], I[v1,v4], P roj

(cid:16) (cid:17) và I[v1,v4] [v1,v4]

là con của . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 6 và đi qua dãy cạnh [v1, v2], [v1, v4]. (cid:17) (cid:16) – Đối với lá

[v1, v4], I[v1,v4], P roj

(cid:17) (cid:17) (cid:16)

[v3, v4], I[v3,v4], P roj

[v1, v3], I[v1,v3], P roj

I[v3,v4] [v3,v4]

I[v1,v3] [v1,v3] [v1, v4], I[v1,v4], P roj

(cid:16) (cid:17) và I[v1,v4] [v1,v4]

[v2, v4], I[v2,v4], P roj

I[v2,v4] ở mức 1 ta lại tiếp tục thực [v2,v4] hiện việc lật I[v2,v4] quanh cạnh [v2, v1] hoặc [v4, v1] để được ảnh nguồn mới tương ứng là I[v2,v1] và I[v4,v1]. (cid:16) Thêm

(cid:17) (cid:17) (cid:16)

[v4, v1], I[v4,v1], P roj

[v2, v1], I[v2,v1], P roj

I[v4,v1] [v4,v1]

I[v2,v1] [v2,v1] [v2, v4], I[v2,v4], P roj

(cid:16) (cid:17) và I[v2,v4] [v2,v4]

(cid:16) (cid:17) – Đối với lá

[v3, v4], I[v3,v4], P roj

(cid:16) (cid:17) (cid:17) và là con của . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 7.88 và đi qua dãy cạnh [v2, v3], [v2, v4]. I[v3,v4] ở mức 1 ta lại tiếp tục thực [v3,v4] hiện việc lật I[v3,v4] quanh cạnh [v3, v1] hoặc [v4, v1] để được ảnh nguồn mới tương ứng là I[v3,v1] và I[v4,v1]. (cid:16) Thêm

[v3, v1], I[v3,v1], P roj

[v4, v1], I[v4,v1], P roj

I[v3,v1] [v3,v1]

I[v4,v1] [v4,v1]

(cid:16) (cid:17)

[v2, v4], I[v2,v4], P roj

I[v2,v4] [v2,v4]

là con của . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 7.88 và đi qua dãy cạnh [v2, v3], [v3, v4].

Hình 2.9 Đường đi ngắn nhất là các đường màu đỏ từ đỉnh nguồn s tới các đỉnh v1, v2, v3, v4.

Tương tự thực hiện từng bước thêm lá và tính các hình chiếu của ảnh nguồn trên cạnh tương ứng ở các mức tiếp theo ta thu được kết quả là đường đi ngắn nhất từ đỉnh nguồn s tới các đỉnh còn lại trên bề mặt của khối đa diện.

Chương 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

Chương này trình bày lại một thuật toán hữu hiệu trong 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 trong không gian ba chiều bằng cách sử dụng “phễu” tương ứng với các cạnh chung của dãy mặt tam giác và lật phẳng mỗi “phễu” đó. Tác giả cũng chỉ ra rằng ảnh của “phễu” sau khi lật sẽ không đè lên nhau [5].

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

Một đường nối hai điểm p và q trong một dãy mặt tam giác của F = {f1, f2, . . . , fm, fm+1} là một đường gấp khúc ∪m i=0[vi, vi+1] với v0 = p, vm+1 = q, mỗi đoạn thẳng [vi, vi+1] nằm trên một tam giác nào đó của F , đỉnh vi (với 1 ≤ i ≤ m) của đường nối giữa p và q thuộc một cạnh chung trong dãy mặt F .

Định nghĩa 3.1.1. [5] Một đường ∪m i=0[vi, vi+1] trong một dãy các tam giác của F = {f1, f2, . . . , fm, fm+1} với v0 = u, vm+1 = v, đoạn thẳng [vi, vi+1] nằm trên một tam giác nào đó của F , mỗi đỉnh vi của đường này thuộc cạnh chung nào đó của F được gọi là đường trắc địa thẳng nhất từ u

Hình 3.1 Đường trắc địa thẳng nhất màu đỏ trên bề mặt khối lập phương tại điểm v1, v3; v1, v3 là

trung điểm của các cạnh chứa nó.

tới v trong F nếu tổng độ lớn các góc của đường này tại các đỉnh vi bằng π. Đường trắc địa thẳng nhất như thế được kí hiệu là CF (u, v).

Chúng ta cũng có thể gọi một đoạn thẳng trên một tam giác fi là một đường trắc địa thẳng nhất. Xét điểm u là một điểm thuộc F và e = [p, q] là một cạnh chung trong F , xét s là điểm chung xa nhất của đường ngắn nhất SP (u, q) nối hai điểm u và q trong F và đường ngắn nhất SP (u, p) nối hai điểm u và p trong F tương ứng với điểm u. Kí hiệu Fpq(s) là miền con của F được bao bởi SP (s, p) và SP (s, q) và [p, q].

Định nghĩa 3.1.2. [5] Miền Fpq(s) được gọi là phễu dọc theo F tương ứng với cạnh chung [p, q], s là chóp của phễu và SP (s, p) và SP (s, q) (để ngắn gọn chúng tôi kí hiệu là B1 và B2) là biên của phễu. Trong trường hợp đơn giản, chúng tôi sẽ kí hiệu phễu là F .

Từ Định nghĩa 3.1.2 có thể thấy rằng một phễu có thể được xây dựng lên từ một dãy mặt tam giác. Giả sử rằng (cid:52)vpq là một tam giác thuộc F nằm khác phía với điểm u qua cạnh chung [p, q]. Tập hợp (cid:98)F = F ∪ (cid:52)pqv được gọi là miền được xử lí của F và v được gọi là điểm tới trực tiếp của F .

Hình 3.2 Phễu được tạo bởi biên B1 = SP (s, p) và B2 = SP (s, q) và cạnh chung [p, q]; (cid:98)F = F ∪(cid:52)pqv

là miền được xử lí.

Lấy u, u(cid:48) ∈ F hoặc u, u(cid:48) ∈ (cid:98)F , việc xây dựng (cid:98)F cũng giống như việc hình thành dãy mặt tam giác, từ đó chúng ta có thể thay thế F bằng (cid:98)F . Khi đó, đường trắc địa thẳng nhất trong phễu mới hình thành sẽ được (cid:98)F (u, u(cid:48)). Giả sử rằng không có phễu nào rỗng thì Fpq(s) với kí hiệu là C s /∈ [p, q], B1 ∩ B2 = {s}, B1 ∩ [p, q] = {p}, B2 ∩ [p, q] = {q}, chúng ta có mệnh đề sau:

Mệnh đề 3.1. [5] Cho một phễu F = Fpq(u) dọc theo dãy mặt tam giác F , z /∈ [p, q], với mỗi i ∈ {1, 2} tồn tại một đường trắc địa thẳng nhất được kí hiệu là Ti trong (cid:98)F đi qua một đỉnh của Bi và gặp đoạn [p, q] tại một điểm duy nhất.

Tiếp theo, luận văn sẽ trình bày lại định lý về các phễu mới sau khi lật không bị đè lên nhau, việc này sẽ làm giảm được các bước tính toán trong quá trình tìm đường đi ngắn nhất giữa hai điểm trên dãy mặt của một tam giác.

Định lý 3.1.1. [5] Ảnh của phễu Fpq(u) thông qua phép lật dọc theo dãy các cạnh của phễu lên mặt phẳng chứa tam giác (cid:52)pqv không bị đè lên nhau, các ảnh của các biên của phễu lồi hướng ra ngoài của (cid:52)¯upq.

Hình 3.3 z là điểm ảnh duy nhất tương ứng với miền đơn Rz = (cid:52)zw1w2 và z(cid:48) là điểm ảnh duy nhất

tương ứng với miền đơn Rz(cid:48) = (cid:52)z(cid:48)w(cid:48)

1w(cid:48) 2.

Chứng minh. Đầu tiên, ta cần chứng minh điểm z và ảnh của nó ¯z là duy nhất tương ứng với miền phễu chứa điểm z. Ta lấy z ∈ F \ [p, q]. Từ Mệnh đề 3.1, chúng ta giả sử rằng: w1 = T ∩ [p, q]; w2 = T ∩ [p, q]. (cid:98)F (z, wi) với i = 1, 2.

Ta gọi: Ti := C Vì T1(z) và T2(z) là các đường đi trắc địa thẳng nhất và dài nhất

xuất phát từ điểm z nên T1(z) và T2(z) là duy nhất.

Từ đó, ta có thể thấy rằng điểm z là điểm duy nhất tương ứng với miền đơn Rz được hình thành bởi các đường trắc địa thẳng nhất T1(z) và T2(z) và [p, q].

Chính vì thế, độ lớn của tất cả các góc của một đường sẽ được bảo toàn qua phép lật phẳng và ảnh của miền Rz tức là Rz là (cid:52)¯zw1w2, dẫn tới ảnh của điểm z là ¯z cũng là duy nhất tương ứng với tam giác Rz.

Giả sử tồn tại hai điểm z, z(cid:48) ∈ F \ [p, q] sao cho Rz = Rz(cid:48) thì bằng cách đưa ra số tam giác trong phễu Fpq(u) mà T1(z) và T2(z) đi qua, chúng ta có thể chứng minh được rằng T1(z) = T1(z(cid:48)) và T2(z) = T2(z(cid:48)) hay điểm z ≡ z(cid:48).

Ta suy ra được ảnh của phễu Fpq(u) thông qua phép lật dọc theo dãy các cạnh của phễu lên mặt phẳng chứa tam giác (cid:52)pqv không bị đè lên nhau. Do độ lớn của tất cả các góc của hai biên B1 và B2 được bảo toàn qua phép lật nên ảnh của hai biên của phễu đều là các đường lồi hướng ra ngoài.

3.2 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

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 trong không gian ba chiều được giới thiệu trong [11]. Từ Định lý 3.1.1 thuật toán được trình bày bằng việc sử dụng ý tưởng phễu tương ứng với các cạnh chung dọc theo dãy mặt tam giác và lật phẳng từng phễu đó, ta gọi thuật toán đó là NFU.

Ta xét F = Fpq(u) là một phễu trong F và B1 = SP (u, p), B2 = SP (u, q) là hai biên của phễu; v là điểm tới và (cid:98)F là miền được xử lí của F . "Phễu" được trình bày như một hàng đợi kết thúc kép mà các đỉnh được sắp xếp theo thứ tự: F = (pr, pr−1. . . . , p1, u, q1, . . . , qs−1, qs), ở đó u = p0 = q0, q = qs, [p, q] là một cạnh chung của F , B1 đi qua các đỉnh p0, p1, . . . , pr và B2 đi qua các đỉnh q0, q1, . . . , qs của F . Phễu dọc theo F tương ứng với cạnh [v, q] (cạnh chung [p, v] cũng tương tự như thế) của F là một phễu mới được xây dựng từ Fpq(u) và điểm tới v.

Giả sử rằng [v, q] là một cạnh chung của F . Quy trình lật phễu mới NFU (F, v, q, u, SP (u, v)) dưới đây để xây dựng một phễu mới tương ứng với cạnh chung [v, q] theo Định lí 3.1.1. Sau khi lật phẳng phễu Fpq(u) lên mặt phẳng chứa (cid:52)pqv, đường đi ngắn nhất từ chóp u đến điểm tới v sẽ được tính toán, chúng ta thực hiện kẻ các đường tiếp tuyến từ v tới các đường lồi hướng ra ngoài B1 và B2 trên mặt phẳng chứa (cid:52)pqv.

Bài toán: Xét một phễu F ⊂ F = {f1, f2, . . . , fm, fm+1}, u là chóp của phễu F , (cid:52)pqv ∈ F , phễu F và (cid:52)pqv có cạnh chung [p, q]. Xây dựng một phễu mới (cid:98)F = F ∪ (cid:52)pqv để tìm đường đi ngắn nhất SP (cid:98)F (u, v) từ u tới v.

Algorithm 3 (Thủ tục lật phễu mới (F, v, q, u, SP

(cid:98)F (u, v)))

(cid:98)F (u, v))

1: Procedure NEWFUNNEL-UNFOLDING (F, v, q, u, SP 2:

Lật F dọc theo dãy các cạnh chung tương ứng của F giữa u và [p, q] lên mặt phẳng chứa (cid:52)pqv.

Đặt B1 và B2 là ảnh sau khi lật của các biên tương ứng B1 và B2 của F. /*Theo Định lý 3.1.1, B1 và B2 là những đường gấp khúc lồi hướng ra phía ngoài của (cid:52)upq.*/

Xác định đường tiếp tuyến từ v tới một trong hai đường gấp khúc B1 và B2 trên mặt phẳng

chứa (cid:52)pqv và vf là tiếp điểm.

Chọn đường trắc địa thẳng nhất C

(cid:98)F (vf , v) mà ảnh của nó là một đoạn thẳng [vf , v] và chọn (cid:98)F (u, vf ) nối u và vf trong (cid:98)F (kí hiệu là B(u, vf ) của biên B1 (nếu vf ∈ B1)

đường ngắn nhất SP hoặc B2 (nếu vf ∈ B2) giữa u và vf .

(cid:98)F (vf , v).

(cid:98)F (u, vf ) ∪ C

(cid:98)F (u, v) = SP

6: 7: 8:

SP Lật tất cả các đỉnh kết thúc phía bên trái (pr) của F cho tới khi chạm vào vf . If chóp của F được lật then chóp của phễu mới sẽ là vf . Thêm v vào điểm kết thúc bên trái của F . Set u := vf , p := v

9: 10: Return < Fpq(u), SP

(cid:98)F (u,v) >

/*F = Fpq(u), SP (cid:98)F (u, v) được cập nhật*/ /*F là một phễu mới tương ứng với cạnh chung F [p, q]).*/

11: End procedure.

Hình 3.4 Minh hoạ dãy mặt tam giác {f1, f2, . . . , f9, f10} trong không gian ba chiều.

Ví dụ 3.2.1. Xét một dãy mặt tam giác gồm có 10 mặt và 12 đỉnh, các đỉnh v0(−3, 3, 3), v1(−3, 0, 3), v2(0, 3, 3), v3(0, 0, 3), v4(0, 0, 0), v5(0, 3, 0), v6(3, 3, 0), v7(3, 0, 0), v8(3, 0, −3), v9(0, 0, −3), v10(0, −3, −3), v11(3, −3, −3). Tìm đường đi ngắn nhất từ đỉnh v0 tới đỉnh v10 trên dãy mặt tam giác đã cho bằng cách sử dụng thuật toán 3.

Hình 3.5 Phễu có chóp là v0 tương ứng với cạnh chung [v1, v2].

Xây dựng một phễu ban đầu F := (cid:52)v0v1v2, chóp phễu là đỉnh v0, hai biên của phễu là hai cạnh của tam giác B1 = SP (v0, v1) = [v0, v1] và B2 = SP (v0, v2) = [v0, v2], cạnh chung là [v1, v2]. Với phễu đầu tiên ứng với cạnh [v1, v2] ta tính được đường đi ngắn nhất từ chóp phễu v0 tới các đỉnh v1, v2 đều bằng 3.

Tiếp tục việc tìm phễu mới bằng việc thực hiện việc lật phễu F lên mặt phẳng chứa tam giác (cid:52)v1v2v3. Trong trường hợp này, phễu F và (cid:52)v1v2v3 cùng nằm trên một mặt phẳng, ta xác định miền được xử lí (cid:98)F (v0, v3)). Khi đó phễu là (cid:98)F := F ∪ (cid:52)v1v2v3, phễu mới (F, v3, v1, v0, SP mới hình thành có chóp là v0, biên mới là B1 = SP (v0, v3) = [v0, v3] và B2 = SP (v0, v2) = [v0, v2] và cạnh chung là [v2, v3]. Với phễu mới hình thành ta tính được đường đi ngắn nhất từ v0 tới đỉnh v3 là 4.24.

Hình 3.6 Phễu (F, v2, v3, v0, SP

(cid:98)F (v0, v3)) tương ứng với cạnh chung [v3, v2].

(cid:98)F (v0, v4)).

Thực hiện việc tìm phễu mới trên dãy mặt tam giác đã cho tương ứng với cạnh [v2, v4] bằng việc lật F lên mặt phẳng chứa (cid:52)v3v2v4. Sau khi xác định được miền được xử lí (cid:98)F := F ∪(cid:52)v3v2v4, phễu mới (F, v4, v3, v0, SP Khi đó phễu mới hình thành có chóp là v0, biên mới là B1 = SP (v0, v4) và B2 = SP (v0, v2) = [v0, v2] và cạnh chung là [v2, v4], ta tính được đường đi ngắn nhất từ v0 tới đỉnh v4 là 6.71.

Tương tự như vậy, khi lật phễu mới hình thành theo cạnh chung [v4, v5], khi đó ta xác định được chóp là v0, miền xử lí (cid:98)F := F ∪ (cid:52)v2v4v5, (cid:98)F (v0, v5)) biên mới là B1 = SP (v0, v4) và B2 = phễu mới (F, v5, v4, v0, SP SP (v0, v5) và cạnh chung là [v4, v5], ta tính được đường đi ngắn nhất từ v0 tới đỉnh v5 là 6.

Hình 3.7 Phễu (F, v4, v2, v0, SP

(cid:98)F (v0, v4)) tương ứng với cạnh chung [v2, v4].

Hình 3.8 Phễu (F, v5, v4, v0, SP

(cid:98)F (v0, v5)) tương ứng với cạnh chung [v4, v5].

Hình 3.9 Phễu (F, v6, v4, v0, SP

(cid:98)F (v0, v6)) tương ứng với cạnh chung [v4, v6].

Hình 3.10 Phễu (F, v7, v4, v0, SP

(cid:98)F (v0, v7)) tương ứng với cạnh chung [v4, v7].

Hình 3.11 Phễu (F, v9, v7, v0, SP

(cid:98)F (v0, v9)) tương ứng với cạnh chung [v7, v9].

Hình 3.12 Đường đi ngắn nhất từ v0 tới đỉnh v4 và phễu (F, v8, v9, v4, SP

(cid:98)F (v4, v8)) tương ứng với

cạnh chung [v9, v8].

Hình 3.13 Đường đi ngắn nhất từ v0 tới đỉnh v4 và phễu (F, v11, v9, v4, SP

(cid:98)F (v4, v11)) tương ứng với

cạnh chung [v9, v11].

Hình 3.14 Đường đi ngắn nhất từ đỉnh v0 tới đỉnh v10 trên dãy mặt tam giác trong không gian

ba chiều.

3.3 Ứ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

Thuật toán NFU tìm đường đi ngắn nhất giữa hai điểm trên dãy mặt tam giác trong không gian ba chiều không những giúp giảm số phép toán trong quá trình tìm đường đi ngắn nhất mà còn có ứng dụng khi tìm đường đi ngắn nhất giữa hai đỉnh của một khối đa diện. Đối với thuật toán thơ ngây trong Ví dụ 2.2.1, việc lật ra nhiều dãy mặt mất rất nhiều thời gian tính toán cũng như là những dãy mặt không hữu dụng, tức là có những dãy mặt được lật ra không xác định đường đi ngắn nhất. Thay vì việc tìm đường đi ngắn nhất từ một điểm nguồn cho trước tới các đỉnh còn lại trên bề mặt một khối đa diện, bài toán được chuyển thành tìm đường đi ngắn nhất từ điểm nguồn cho trước tới một đỉnh còn lại của khối đa diện và sử dụng thuật toán NFU.

Ví dụ sau đây sẽ làm rõ được tính ứng dụng của thuật toán NFU so

với thuật toán thơ ngây.

Ví dụ 3.3.1. Xét một khối đa diện mà các mặt đã được tam giác phân thành 16 mặt (xem hình 2.8) và các đỉnh s(1.5, 1.5, 6), v1(0, 0, 3), v2(3, 0, 3), v3(3, 3, 3) v4(0, 3, 3), v5(0, 0, 0), v6(3, 0, 0), v7(3, 3, 0), v8(0, 3, 0), v9(1.5, 1.5, −3). Tìm đường đi ngắn nhất từ đỉnh nguồn s tới các đỉnh còn lại trên bề mặt của khối đa diện bằng cách sử dụng thuật toán dùng nguồn sáng và thuật toán NFU.

Bây giờ ta sẽ thực hiện giải ví dụ trên bằng hai thuật toán: thuật

toán thơ ngây và thuật toán NFU.

Sử dụng thuật toán “thơ ngây” để giải bài toán: Trong ví dụ này ta có thể chỉ ra được đường đi ngắn nhất trên bề mặt khối đa diện từ đỉnh s lần lượt tới các đỉnh v1, v2, v3, v4 đều bằng 3.67, đường đi ngắn nhất từ s tới v5, v6, v7, v8 đều bằng 6.5287, đường đi ngắn nhất trên bề mặt khối đa diện từ s tới v9 bằng 9.7 và đi qua dãy cạnh {[v1, v2], [v2, v5], [v5, v6]}.

Hình 3.15 Minh hoạ khối đa diện trong không gian ba chiều trong Ví dụ 3.3.1.

(cid:136) Bước 1: Ta gán: root:= s;

Hình 3.16 Minh hoạ ∠((cid:52)Sv1v2, (cid:52)v1v2v5) trong không gian ba chiều.

Các cạnh: [v1, v2], [v2, v3], [v3, v4], [v4, v1] là các cạnh đối diện với gốc s. Khi đó: ([v1, v2], s, [v1, v2]), ([v2, v3], s, [v2, v3]), ([v3, v4], s, [v3, v4]), ([v4, v1], S, [v4, v1]) là con của gốc s. Khoảng cách từ đỉnh s tới lần lượt các đỉnh v1, v2, v3, v4 đều bằng 3.67.

(cid:136) Bước 2: Do khối đa diện này sau khi các mặt được tam giác phân sẽ

I[v1,v5] [v1,v5] của ảnh nguồn I[v1,v5] lên

có tất cả 16 mặt nên cây chúng tôi xây dựng sẽ có 16 mức. Mức 1: Đối với ([v1, v2], s, [v1, v2]), ([v2, v3], s, [v2, v3]), ([v3, v4], s, [v3, v4]), ([v4, v1], s, [v4, v1]) là lá ta thực hiện lật s lần lượt quanh các cạnh [v1, v2], [v2, v3], [v3, v4], [v4, v1], ta nhận thấy (xem hình 3.16): ∠((cid:52)Sv1v2, (cid:52)v1v2v5) = 153o43o; ∠((cid:52)Sv3v4, (cid:52)v3v4v7) = 153o43o; ∠((cid:52)Sv2v3, (cid:52)v2v3v6) = 153o43o; ∠((cid:52)Sv4v1, (cid:52)v4v1v8) = 153o43o. Ở mức 1 này, ta thực hiện lật s lần lượt qua các cạnh [v1, v2], [v2, v3], [v3, v4], [v4, v1] lên mặt phẳng chứa các mặt (cid:52)v1v2v5, (cid:52)v2v3v6, (cid:52)v3v4v7, (cid:52)v4v1v8 và ảnh của s tương ứng trên mỗi mặt phẳng lật là I[v1,v2], I[v2,v3], I[v3,v4], I[v4,v1]. Đối với (cid:52)sv1v2 và (cid:52)v1v2v5 sau khi đồng phẳng, ta gán e(cid:48) := [v1, v5], [v2, v5] và thực hiện tính hình hình chiếu P roj

I[v2,v5] [v2,v5] của ảnh nguồn I[v2,v5] lên cạnh [v2, v5]. (cid:17)

cạnh [v1, v5] và P roj (cid:16) (cid:17) Thêm và là con

[v1, v5], I[v1,v5], P roj

I[v2,v5] [v2,v5]

I[v1,v5] [v1,v5]

(cid:16) [v2, v5], I[v2,v5], P roj

của ([v1, v2], s, [v1, v2]). Từ đây, ta tính được đường đi ngắn nhất từ s tới đỉnh v5 bằng 6.5287 đi qua cạnh [v1, v2].

(cid:16) (cid:17)

[v2, v5], I[v2,v5], P roj

I[v2,v5] [v2,v5]

(cid:16)

[v5, v6], I[v5,v6], P roj

Tương tự đối với (cid:52)sv2v3 và (cid:52)v2v3v6, (cid:52)sv3v4 và (cid:52)v3v4v7, (cid:52)sv4v1 và (cid:52)v4v1v8 ta sẽ tính được đường đi ngắn nhất từ s tới các đỉnh v6, v7, v8 và cùng bằng 6.5287. Mức 2: Đối với lá ta lại tiếp tục thực hiện việc lật I[v2,v5] quanh cạnh [v2, v5] hoặc [v1, v5] để được ảnh nguồn mới tương ứng là I[v2,v5] và I[v1,v5]. Từ đây ta sẽ tính được đường đi ngắn nhất từ I[v2,v5] tới đỉnh v6 và bằng 6.5287. Các lá khác ở mức này ta cũng làm tương tự để tìm được đường đi ngắn nhất từ ảnh nguồn tới các đỉnh v7, v8. (cid:17) I[v5,v6] [v5,v6]

Mức 3: Đối với lá ta lại tiếp tục thực hiện việc lật I[v2,v5] quanh cạnh [v5, v6] để được ảnh nguồn mới tương ứng là I[v5,v6]. Từ đây ta sẽ tính được đường đi ngắn nhất từ I[v5,v6] tới đỉnh v9 và bằng 9.7.

Hình 3.17 Minh hoạ đường đi ngắn nhất từ I[v1v2] đến v5 trong không gian ba chiều.

Hình 3.18 Minh hoạ đường đi ngắn nhất từ I[v2,v5] đến v6 trong không gian ba chiều.

Tiếp tục việc lật và tính toán các hình chiếu như thế cho tới mức thứ 16, tất cả các đường đi ngắn nhất từ điểm nguồn s tới các đỉnh còn lại sẽ được tính.

Hình 3.19 Minh hoạ đường đi ngắn nhất từ I[v5,v6] đến v9 trong không gian ba chiều.

Sử dụng thuật toán NFU để giải bài toán: Đối với thuật toán NFU, để tìm đường ngắn nhất từ điểm nguồn s tới các đỉnh còn lại trên bề mặt của khối đa diện, ta chuyển bài toán thành các bài toán nhỏ. Đối với các đỉnh kề với đỉnh s như v1, v2, v3, v4 ta có thể tìm ra luôn được đường đi ngắn nhất từ điểm nguồn s tới các đỉnh đó. Đối với các đỉnh v5, v6, v7, v8, v9, ta cần tìm tất cả các dãy mặt chứa các đỉnh s hoặc v5, s hoặc v6, s hoặc v7, s hoặc v8, s hoặc v9 và sử dụng thuật toán NFU để tìm đường đi ngắn nhất trên từng dãy mặt. Sau khi tìm được các đường đi ngắn nhất đó ta so sánh các đường đi ngắn nhất có cùng điểm nguồn và điểm tới với nhau và chọn ra đường đi ngắn nhất.

Như vậy, khi sử dụng thuật toán NFU để giải bài toán tìm đường đi ngắn nhất từ một điểm nguồn tới các đỉnh còn lại trên bề mặt của khối đa diện số các phép toán đã được giảm đi rất nhiều so với việc sử dụng thuật toán thơ ngây.

Hình 3.20 Đường đi ngắn nhất màu đỏ từ đỉnh nguồn s tới các đỉnh trên bề mặt khối đa diện.

Hình 3.21 Dãy tam giác đã chọn được tô màu xanh trong Ví dụ 3.2.1 chứa hai đỉnh v0 và v10.

Để lược bỏ những dãy mặt mà đường đi ngắn nhất từ đỉnh nguồn tới đỉnh cần tìm không phải là đường ngắn nhất trên bề mặt của khối đa diện, ta cùng xét lại dãy mặt trong Ví dụ 3.2.1 là một dãy mặt tam giác của khối đa diện như Hình 3.21.

Hình 3.22 Đường đi ngắn nhất màu đỏ thuộc dãy mặt màu xanh đã chọn trên bề mặt khối đa diện.

Trong Ví dụ 3.2.1 đường đi ngắn nhất v0 tới v10 là đường màu đỏ đi qua đỉnh v4 và đỉnh v9 nhưng đối với khối đa diện dưới đây thì nó không còn là đường đi ngắn nhất từ đỉnh v0 tới đỉnh v10 trên bề mặt của khối đa diện.

Để đảm bảo được rằng đường đi ngắn nhất từ điểm nguồn tới đỉnh cần tìm là ngắn nhất trên bề mặt của khối đa diện luận văn sẽ sử dụng kỹ thuật cập nhật dãy mặt tam giác mới được Valérie Pham-Trong, Nicolas Szafran và Luc Biard trình bày năm 2001 [6]. Trong trường hợp đường đi ngắn nhất trên một dãy mặt tam giác khi đã được lật phẳng là một đoạn thẳng thì bài toán tìm đường đi ngắn nhất được giải quyết, còn nếu đường đi ngắn nhất trên một dãy mặt tam giác khi lật phẳng là một đường gấp khúc (gấp tại các đỉnh có tổng số đo lớn hơn 180o - đỉnh xoay) thì thuật toán sẽ cập nhật một dãy mặt mới quanh đỉnh xoay đó. Họ cũng chứng minh được rằng đường ngắn nhất trên dãy mặt mới cập nhật chỉ có thể nhỏ hơn hoặc bằng đường ngắn nhất trên dãy mặt trước khi cập nhật. Áp dụng kĩ thuật đó để giải bài toán trong Ví dụ 3.3.1, ta có thể chọn ra được một dãy mặt mới (xem Hình 3.23).

Hình 3.23 Chọn dãy mặt mới màu tím xoay quanh đỉnh v5 chứa đường đi ngắn nhất giữa hai đỉnh

v0 và v10 khác.

Hình 3.24 Đường đi ngắn nhất màu đỏ từ v0 tới v10 trên dãy mặt tam giác mới.

Sử dụng thuật toán NFU để tìm đường đi ngắn nhất từ đỉnh v0 tới đỉnh v10 trên dãy mặt tam giác mới cập nhật ta thu được đường đi ngắn nhất tốt hơn đường đi ngắn nhất khi chưa cập nhật dãy mặt tam giác (xem Hình 3.24).

KẾT LUẬN

Luận văn này được trình bày theo ba chương với nội dung chính là giải quyết bài toán tìm đường đi ngắn nhất giữa hai điểm trên dãy mặt tam giác trong không gian ba chiều bằng ý tưởng “phễu” có sử dụng kĩ thuật lật phẳng. Từ đó phát triển thuật toán bằng việc xây dựng tìm đường đi ngắn nhất từ một điểm nguồn tới các đỉnh còn lại trên bề mặt của khối đa diện bằng việc lựa chọn một dãy mặt tam giác khác.

(cid:136) Chương 1: Nội dung chính trong chương này là giải quyết bài toán tìm đường đi ngắn nhất giữa hai điểm trong một đa giác đơn. Đây là bài toán được giải trong không gian hai chiều có sử dụng kỹ thuật “phễu”.

(cid:136) Chương 2: Chương này trình bày về kỹ thuật lật phẳng một dãy mặt tam giác của một dãy mặt tam giác đã cho trước và sau đó đưa ra thuật toán dùng nguồn sáng và bóng (thuật toán Thơ ngây) để xác định đường đi ngắn nhất từ một điểm nguồn tới các đỉnh còn lại trên bề mặt của một khối đa diện. Sau đó, luận văn cũng đưa ra một ví dụ để minh hoạ cho thuật toán, đồng thời cũng cho thấy được sự cồng kềnh của số các phép toán trong việc tính toán đường đi ngắn nhất.

(cid:136) Chương 3: Chương cuối cùng trình bày lại 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 bằng cách sử dụng kĩ thuật lật phẳng các mặt tam giác và ý tưởng “phễu” (thuật toán NFU). Luận văn cũng đưa ra một ứng dụng của thuật toán NFU trong việc 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 bằng cách lựa chọn một dãy mặt tam giác khác chứa hai điểm cần tìm đường đi ngắn nhất.

Tài liệu tham khảo

[1] P. K. Agarwal, S. Har-Peled, M. Karia. Computing approximate short- est paths on convex polytopes. Algorithmica. 2002;33(2):227–242.

[2] J. A. Sethian. Fast marching methods. SIAM Rev. 1999;41(2):199–235.

[3] S. Nazari, M. R. Meybodi, M. A. Salehigh, S. Taghipour. An advanced algorithm for finding shortest path in car navigation system. 2008 First International Conference on Intelligent Networks and Intelligent Sys- tems. 2008;671-674.

[4] V. Akman. Geometry and graphics applied to robotics. Theoreti- cal foundations of computer graphics and CAD NATO ASI Series. 1988;40:619-638.

[5] P. T. An. Finding Shortest paths in a sequence of triangles in 3D by the planar unfolding. Numerical Functional Analysis and Optimization. 2019; 40(8):1532-2467.

[6] V. P. Trong, N. Szafran, L. Biard. Pseudo-geodesics on threedimen- sional surfaces and pseudo-geodesic meshes. Numerical Algorithms. 2001;26(4):305-315.

[7] D. T. Lee, F. P. Preparata. Euclidean shortest paths in the presence of

rectilinear barries. NETWORKS. 1984;14(3):393-410.

[8] M. Sharir, A. Schorr. On shortest paths in polyhedral spaces. SIAM

Journal on Computing. 1986; 15(1):193-215.

[9] J. S. B. Mitchell, D. M. Mount, C. H. Papadimitriou. The discrete geodesic problem. SIAM Journal on Computing. 1987; 16(4):647-668.

[10] J. Chen, Y. Han. Shortest paths on a polyhedron, Part I: Computing shortest paths. International Journal of Computational Geometry and Applications. 1990; 6(2):360-369.

[11] D. M. Mount. On finding shortest paths on convex polyhedra. Mary-

land Univ College Park Center for Automation Research. 1985.

[12] P. T. An. Finding shortest paths in a sequence of triangles in 3D by

method of orienting curves. Optimization. 2018; 67(1):159-177.

[13] E. W. Dijkstra. A note on two problems in connection with graphs.

Numerische Mathematik. 1959;1:269–271.

[14] P. R. Evans. Rotations and rotation matrices. Acta Crystallographica

Section D, Acta Cryst. 2001;57:1355-1359.

[15] R. J. Wilson. Introduction to graph thery. Fourth edison. Addison Wes- ley Longman Limited. Edinburgh Gate, Harlow, Essex CM20 2JE, Eng- land. 1996.