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 Của Khối Đa Diệ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 Của Khối Đa Diện

Tác giả: Nguyễn Thị Mỹ Hạnh

Lĩnh vực: Toán ứng dụng

Nội dung tài liệu:

Luận văn này tập trung vào việc tìm kiếm đường đi ngắn nhất trên bề mặt của khối đa diện, một vấn đề quan trọng trong nhiều lĩnh vực 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. Nghiên cứu này đề xuất các thuật toán để giải quyết bài toán tìm đường đi ngắn nhất giữa hai điểm trên một đa giác đơn, trên bề mặt khối đa diện và trên một dãy mặt tam giác trong không gian ba chiều. Cụ thể, luận văn giới thiệu các khái niệm nền tảng như lý thuyết đồ thị, đa giác đơn, cây đối ngẫu, hình ống tay và hình “phễu”. Luận văn trình bày các thuật toán đã được phát triển bởi các nhà nghiên cứu trước đó, bao gồm thuật toán “Phễu” của Lee và Preparata (1984), thuật toán tìm đường đi ngắn nhất giữa các đỉnh trên bề mặt khối đa diện của Chen và Han (1990), và ứng dụng kỹ thuật “phễu” của An (2019) để giải quyết bài toán. Nghiên cứu cũng đưa ra các ví dụ minh họa và phân tích về độ phức tạp của các thuật toán được đề cập.

Mục lục chi tiết:

• Lời cam đoan
• Lời cảm ơn
• Danh mục kí hiệu
• Mở đầu
• Chương 1: Tìm đường đi ngắn nhất giữa hai điểm trong đa giác đơn
• Chương 2: Tìm đường đi ngắn nhất 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
• Kết luận
• Tài liệu tham khảo