Luận văn: 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 khối đa diện

Khám phá luận văn về kỹ thuật phễu và cây phễu trong việc tìm đường đi ngắn nhất trên bề mặt khối đa diện. Tìm hiểu ứng dụng và phương pháp.

• Tác giả: An
• Chuyên ngành: Toán học
• Đề tài: Tìm đường đi ngắn nhất trên bề mặt khối đa diện
• Loại tài liệu: Luận văn

Tóm tắt

I. Tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn

Chương này trình bày các khái niệm cơ bản trong lý thuyết đồ thị và thuật toán tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn. Để giải quyết bài toán này, cần hiểu rõ về đồ thị, cây đối ngẫu và hình ống tay. Đa giác đơn được định nghĩa là một chuỗi các điểm nối với nhau mà không cắt nhau. Đường đi ngắn nhất giữa hai điểm s và t trong đa giác đơn không được cắt biên của đa giác. Lee và Preparata đã phát triển thuật toán với độ phức tạp O(n log n) để tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn. Họ đã chỉ ra rằng đường đi ngắn nhất sẽ cắt các đường chéo của đa giác tại các điểm duy nhất. Điều này dẫn đến việc xây dựng một cây G với gốc là điểm s, từ đó tìm ra đường đi ngắn nhất. Việc xác định hình ống tay giúp giảm bớt số lượng đỉnh cần xem xét, từ đó tối ưu hóa quá trình tìm kiếm.

1.1 Đồ thị cây và chu trình cây đối ngẫu

Đồ thị vô hướng G được định nghĩa là một cặp (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh. Một hành trình trong G là một dãy các đỉnh nối với nhau qua các cạnh. Cây đối ngẫu của một đa giác đơn là một đồ thị mà các đỉnh tương ứng với các tam giác trong đa giác. Việc xây dựng cây đối ngẫu giúp xác định đường đi ngắn nhất giữa hai điểm trong đa giác đơn. Đường đi ngắn nhất sẽ cắt các đường chéo của đa giác tại các điểm duy nhất, từ đó tạo thành một đường gấp khúc. Điều này cho thấy tầm quan trọng của việc hiểu rõ về đồ thị và cây đối ngẫu trong việc giải quyết bài toán tìm đường đi ngắn nhất.

1.2 Hình ống tay và hình phễu

Hình ống tay là một miền trong đa giác đơn chứa đường đi ngắn nhất giữa hai điểm s và t. Để xác định hình ống tay, cần tìm miền chứa đường đi ngắn nhất. Lee và Preparata đã giới thiệu khái niệm về phễu, một miền được giới hạn bởi các đường đi ngắn nhất từ s tới các điểm đầu mút của các đường chéo. Phễu giúp giảm bớt số lượng đỉnh cần xem xét, từ đó tối ưu hóa quá trình tìm kiếm. Việc xác định phễu cũng giúp đảm bảo rằng đường đi ngắn nhất nằm trong đa giác đơn, từ đó tạo điều kiện thuận lợi cho việc áp dụng thuật toán tìm đường đi ngắn nhất.

II. Tìm đường đi ngắn nhất trên bề mặt của khối đa diện

Chương này trình bày quy trình lật phẳng một dãy mặt tam giác trong không gian ba chiều để tìm đườ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 khối đa diện. Kỹ thuật lật phẳng giúp chuyển bài toán từ không gian ba chiều về không gian hai chiều mà không làm mất đi độ chính xác về khoảng cách. Điều này rất quan trọng trong việc tối ưu hóa các thuật toán tìm đường đi ngắn nhất. Bằng cách sử dụng thuật toán nguồn sáng và bóng, có thể xác định đường đi ngắn nhất 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. Việc áp dụng thuật toán này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong các lĩnh vực như robot và hệ thống thông tin địa lý.

2.1 Phép lật

Phép lật là một kỹ thuật quan trọng trong việc tìm đường đi ngắn nhất trên bề mặt khối đa diện. Khi thực hiện phép lật, các mặt tam giác được đưa lên mặt phẳng mà không làm mất đi độ chính xác về khoảng cách giữa các điểm. Điều này cho phép xác định đường đi 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. Kỹ thuật này giúp đơn giản hóa bài toán và làm cho việc tính toán trở nên hiệu quả hơn. Việc lật phẳng các mặt tam giác cũng giúp bảo toàn các góc trong tam giác, từ đó đảm bảo tính chính xác của các phép tính liên quan đến khoảng cách.

2.2 Thuật toán dùng nguồn sáng và bóng

Thuật toán sử dụng nguồn sáng và bóng là một phương pháp hiệu quả để tìm đường đi ngắn nhất trên bề mặt khối đa diện. Bằng cách xác định các bóng của điểm nguồn lên các cạnh, có thể tìm ra đường đi ngắn nhất tới các đỉnh còn lại. Thuật toán này không chỉ đơn thuần là một phương pháp lý thuyết mà còn có ứng dụng thực tiễn trong việc tối ưu hóa các hệ thống điều hướng và robot. Việc áp dụng thuật toán này giúp giảm thiểu thời gian và công sức trong việc tìm kiếm đường đi ngắn nhất, từ đó nâng cao hiệu quả trong các ứng dụng thực tế.

III. 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 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. Thuật toán này sử dụng ý tưởng về phễu và kỹ thuật lật phẳng để xác định đường đi ngắn nhất. Việc xác định phễu mới qua phép lật phẳng giúp đảm bảo rằng đường đi ngắn nhất không bị đè lên nhau. Điều này rất quan trọng trong việc tối ưu hóa quá trình tìm kiếm. Thuật toán này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong việc giải quyết các bài toán phức tạp trong không gian ba chiều, từ đó mở ra nhiều cơ hội nghiên cứu mới trong lĩnh vực hình học tính toán.

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

Đường trắc địa thẳng nhất giữa hai điểm trong không gian ba chiều được xác định thông qua các phễu dọc theo dãy mặt tam giác. Việc xác định các phễu này giúp tối ưu hóa quá trình tìm kiếm đường đi ngắn nhất. Các phễu được giới hạn bởi các đường đi ngắn nhất từ điểm nguồn tới các đỉnh của dãy mặt tam giác. Điều này đảm bảo rằng đường đi ngắn nhất không bị đè lên nhau và luôn nằm trong miền của đa diện. Việc áp dụng thuật toán này không chỉ giúp giải quyết bài toán tìm đường đi ngắn nhất mà còn mở ra nhiều hướng nghiên cứu mới trong lĩnh vực hình học tính toán.

3.2 Ứ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 được áp dụng để 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. Việc sử dụng thuật toán này giúp tối ưu hóa quá trình tìm kiếm và giảm thiểu thời gian tính toán. Ứng dụng của thuật toán NFU không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong các lĩnh vực như robot và hệ thống thông tin địa lý. Việc tìm đường đi ngắn nhất trên bề mặt khối đa diện có thể giúp cải thiện hiệu suất của các hệ thống điều hướng, từ đó nâng cao hiệu quả trong các ứng dụng thực tế.

Trích đoạn nội dung tài liệu

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

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. [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.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 ]. 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.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.4 Minh hoạ một đồ thị vô hướng. [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. Bậc của v là số các đỉnh kề với v.

Khi đó G là một đồ thị vô hướng được biểu diễn như Hình 1. [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, 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.

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

[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. 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 .6 Đa giác đơn được P được tam giác phân bởi các đường chéo.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à π. 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.

[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,. 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.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. [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 .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.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. [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. [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. 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 .