Chương 1 Kiến thức chuẩn bi 1.1 Bài toán tìm đường đi ngắn nhất giữa hai điểm trên bề mặt địa hình Tính toán đường đi ngắn nhất giữa hai điểm trên một miền trong 2D và trên bề mặt đa diện trong 3D là những vấn đề kinh điển trong hình học tính toán và được ứng dụng trong nhiều lĩnh vực như robot, hệ thống thông tin địa ly (GIS) và điều hướng,. Đến thời điểm hiện tại, những vấn đề trên đã được nghiên cứu chuyên sâu, tuy nhiên hiện nay đây vẫn là một chủ đề nhận được sự quan tâm của nhiều nhà khoa học trên thế giới với nhiều bài toán mở chưa được giải quyết, chang hạn như bài toán tìm đường đi ngắn nhất chính xác ít dốc hay một xu hướng nghiên cứu đang nhận được nhiều sự quan tâm hiện nay đó là việc sử dụng nấm nhay để tìm đường đi tối ưu giữa hai điểm trên bề mặt địa hình trong 3D,. Bài toán về đường đi ngắn nhất: Cho hai điểm s và f trên mặt địa hình 7, tìm đường đi ngắn nhất từ s đến t sao cho nó nằm trên mặt địa hình 7. Để giải bài toán đường đi ngắn nhất chính xác, Sharir và Schorr [39] lần đầu tiên trình bay một thuật toán O(n? log ø) chạy trên một mặt đa diện lồi, trong đó ø là số đỉnh của đa diện.
Thuật toán này sau đó đã được cải tiến bởi Mount [30] thành O(n? logn). Thuật toán của Mount [30] dựa trên 3 quan sát rất quan trọng sau: 1. Giả sử rằng đường đi ngắn nhất từ điểm s đến điểm tf trên bề mặt khối đa diện lồi đi 1 ‘Scene Graph: visible and active geometries [ED <tab> cwitches scene graph onfof TT Geometries Cl Specials 1 Quick Preferences Hình 1.1: Đường đi ngắn nhất nối hai điểm s và £ trên một mặt địa hình đã được tam giác phân (đường được in đậm) được mô phỏng và tính toán bằng phần mềm JavaView. qua phần trong của dãy các cạnh e,.
Khi đó, nếu lật phẳng dãy mặt tam giác tương ứng với dãy cạnh trên thì đường đi ngắn nhất từ s đến ¢ trên dãy mặt tam giác ấy có dạng một đoạn thing. Hai đường đi ngắn nhất xuất phát từ cùng một điểm đến hai điểm khác nhau trên bề mặt khối đa diện lồi không cắt nhau (ngoại trừ trường hợp đường ngắn nhất này là tập con của đường đi ngắn nhất kia). Một đường đi ngắn nhất bất kỳ (trừ điểm đầu và điểm cuối) không đi qua đỉnh của khối đa diện lồi. Đối với một bề mặt đa diện tùy ý, kế thừa mô hình của thuật toán Dijkstra [18], Mitchell, Mount va Papadimitriou [29] đã đưa ra một thuật toán có độ phức tạp O(n” logn).
Việc triển khai thuật toán tìm đường đi ngắn nhất chính xác này đã được thực hiện bởi Surazhsky và cộng sự [40] với một số cải tiến và mở rộng vào năm 2005. Năm 1996, Chen và Han [15] đã đưa ra thuật toán có độ phức tap O(n?) dựa trên quan sát chính về “one angle one split” để xác định đường đi ngắn nhất từ một điểm nguồn đã cho đến các đỉnh bất kỳ trên bề mặt khối đa diện. Về mặt lý thuyết, thuật toán của Chen và Han đạt được độ phức tạp tiệm cận tốt nhất cho đến nay, tuy nhiên, hiệu suất thực tế của nó là kém (xem [17]). Thuật toán này được Kaneva và O’Rourke [24] thực hiện vào năm 2000.
Ngoài ra, Kapoor [26] đã cả tiến thuật toán này bằng cách sử dụng phương pháp wavefront. Ngoài một số tác giả chúng tôi đã đề cập ở trên, một số nhà toán học Việt Nam cũng đi sâu nghiên cứu và có nhiều đóng góp cho lý thuyết cũng như ứng dụng trong việc giải quyết các van đề của Hình học tính toán nói chung và bài toán tìm đường di ngắn nhất nói riêng tiêu biểu như (theo Alphabet): Phan Thành An, Hoàng Nam Dũng, Nguyễn Ngọc Hải, Trần Văn Hoài, Hoàng Xuân Phú, Lê Hồng Trang,. Để giải bài toán đường đi ngắn nhất khi miền là các bề mặt đa diện, một số tác giả đã xem xét bài toán tìm đường đi ngắn nhất giữa hai điểm bên trong một dãy mặt tam giác (được xây dung từ bề mặt đa diện), chang han, [32], [41]. Kỹ thuật lật phẳng day mặt tam giác, với tính chất bảo toàn góc và khoảng cách, thường được sử dụng để giải quyết vấn đề này.
Cụ thể, Pham-Trong và cộng sự trong [32] đã đưa ra một thuật toán để tìm đường đi ngắn nhất giữa hai điểm bên trong một dãy các mặt liền kề. Đầu tiên, họ chọn một dãy mặt tam giác bất kỳ nối hai điểm mà họ cần xác định đường đi ngắn nhất, sau đó họ sử dụng kỹ thuật lật phẳng để đưa dãy các tam giác liền kề trong 3D về một dãy mặt tam giác trong 2D. Tiếp đó, họ sử dụng kỹ thuật "beam propagation" để tìm đường đi ngắn nhất giữa hai điểm trong dãy mặt tam giác trong 2D mới thu được để từ đó thu được đường đi ngắn nhất giữa hai điểm trên dãy mặt trong 3D. Sau đó, họ làm mới dãy mặt dựa trên đường đi ngắn nhất vừa tìm được trên dãy mặt trước đó và lặp lại cho đến khi tìm được dãy mặt chứa đường đi ngắn nhất địa phương trên bề mặt khối đa diện.
Tuy nhiên, Pham-Trong và cộng sự trong [32] đã không trình bày chi tiết thuật toán cũng như đưa ra độ phức tạp của thuật toán. Vào năm 2007, Xin va Wang [41], kế thừa ý tưởng của Pham- Trong và cộng sự, đã giới thiệu quá trình lật phẳng một chuỗi các mặt kề và một thuật toán để tính toán đường đi ngắn nhất giữa hai điểm bên trong dãy mặt đã được lật phẳng. Do phức tap tính toán của Thuật toán Xin-Wang [41] là O(n’), trong đó n là số cạnh kề của dãy mặt tam giác. Tóm lai, các kết quả nghiên cứu trên đều có một điểm chung đó là sử dụng kỹ thuật lật phẳng để đưa 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 3D về 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 2D.
Tuy nhiên trong thực tế, ảnh của dãy mặt tam giác sau khi thực hiện kỹ thuật lật phẳng có thể xảy ra trường hợp các mặt đè lên nhau. Trong các tài liệu [32] và [41], cả Pham-Trong và cộng sự cũng như Xin-Wang đều không đề cập tới và không chứng minh về tính đúng đắn của thuật toán của họ trong trường hợp như vậy. Do đó, việc làm thế nào để xác định được đường đi ngắn nhất giữa hai điểm trong 3D mà không sử dụng kỹ thuật lật phẳng được đặt ra một cách tự nhiên. Xuất phát từ lí do trên, An trong [11] và [13] đã nghiên cứu việc tìm đường đi ngắn nhất giữa hai điểm trên dãy mặt tam giác trong 3D mà không cần sử dụng kỹ thuật lật phẳng bằng cách sử dụng ý tưởng hình học của phương pháp Đường định hướng.
Phương pháp Đường định hướng được đưa ra bởi Phú [33] vào năm 1987 để giải bài toán Steiner về việc tìm đa giác có chu vi nhỏ nhất nội tiếp bên trong một đa giác lồi, bằng cách chỉ sử dụng thước kẻ và compa. Sau đó, phương pháp này được phát triển thêm trong các tài liệu khác như [19], [20], [34], [36]. Hơn nữa, phương pháp nay đã thành công khi áp dụng để giải quyết một số bài toán khác nữa, chẳng hạn như bài toán điều khiển tối ưu của các nhà máy thủy điện, bài toán điều hướng của Zermelo dọc theo một con sông, bài toán kiểm kê tối ưu và kiểm soát tối ưu thời gian của người thao tác dọc theo quỹ đạo quy định (xem [13]). Gần đây, An nhận thấy rằng ý tưởng của phương pháp Đường định hướng có thể được áp dụng thành công để giải các bài toán khác nhau của hình học tính toán.
Một số kết quả đầu tiên theo hướng này đã được trình bày trong [7], [8], trong đó, An va cộng sự đã đưa ra một số thuật toán hiệu quả để xác định bao lồi của một tập hợp hữu han các điểm trong 2D và 3D. Vào năm 2017, An [11] đã sử dụng phương pháp Đường định hướng để đưa ra khái niệm về phễu ứng với một cạnh kề trên dãy tam giác trong không gian ba chiều (tương tự như của Lee và Preparata trong một đa giác đơn [27]), đường đi ngắn nhất nối hai điểm trong dãy tam giác được xác định bằng đỉnh của phéu liên kết với các cạnh chung dọc theo dãy tam giác. Bằng việc sử dụng phương pháp Đường định hướng, An [11] đã chỉ ra rằng mỗi phễu như vậy được xây dựng mà không cần sử dung kỹ thuật lật phẳng. Trong luận văn này, chúng tôi trình bày kết quả nghiên cứu gần nhất của An, Phú [13] về việc sử dụng phương pháp Đường định hướng ở dạng tường minh để xác định đường đi ngắn nhất chính xác giữa hai điểm trên dãy các mặt tam giác liền kề trong 3D.
Bên cạnh đó, chúng tôi cũng tìm hiểu một xu hướng nghiên cứu gần đây đó là tìm đường đi ngắn nhất trong 3D bằng cách sử dung nấm nhay.2 Đường đi và đường đi ngắn nhất trên dãy mặt tam giác Đầu tiên, ta trình bày một số khái niệm cơ bản sau. Khoi đa điện trong không gian R® được xác định bởi một tập hữu hạn các đa giác sao cho mỗi cạnh của đa giác này trùng với đúng một cạnh của đa giác khác (tức là các đa giác kề nhau). Khi đó, các đỉnh và các cạnh của đa giác cũng là các đỉnh và cạnh của khối đa diện (xem [28|). Một mặt đa diện là một hợp của một số hữu hạn các mặt đa giác, trong đó hai đa giác bất kỳ đều có một cạnh chung, một đỉnh chung hoặc không có phần tử chung, và mỗi cạnh thuộc nhiều nhất hai đa giác (xem [28]).
Trong luận văn này, chúng tôi giả thiết rằng bề mặt của các khối đa diện bao gồm các mặt dạng tam giác. Với mỗi điểm q € R có tọa độ gr, dy, G, trong đó q; là cao độ của điểm gq. Khi đó, ta có định nghĩa sau. (xem [2]) Một địa hành (terrains) 7 là đồ thị của một ham liên tục ƒ: R? — R đặt tương ứng mỗi điểm trên mặt phẳng ngang với một cao độ.
Trong luận văn này bề mặt địa hình được mô tả bởi một mạng lưới tam giác không đều TIN (Triangular Irregular Network).2: Một mặt địa hình thu được từ một tập các điểm trong mặt phẳng. Mỗi cạnh của một tam giác nếu xác định biên của địa hình thì nó chỉ thuộc một mặt tam giác, trong trường hợp ngược lại nó kề bởi đúng hai tam giác.