Người báo cáo: Đặng Thị Ngọc Ánh
Thời gian: 9h, Thứ 4, ngày 21/9/2016
Địa điểm: Phòng số 4, nhà A14, Viện Toán học, 18 Hoàng Quốc Việt, Hà Nội
Tóm tắt: Bài toán tìm đường đi ngắn nhất giữa hai điểm trong một miền hình học là một trong những vấn đề cơ bản của lĩnh vực hình học tính toán. Bài toán này trong không gian 2 chiều với miền hình học là đa giác đơn đã được giải quyết với nhiều thuật toán nhưng có độ phức tạp về thời gian là O(n2), báo cáo này trình bày thuật toán sử dụng kỹ thuật “phễu” của Lee và Preparata đăng trên tạp chí Networks (1984) với thời gian chỉ còn O(n). Thuật toán được phát triển bằng cách xây dựng các hình phễu mà đường đi ngắn nhất thuộc vào cạnh biên của các hình phễu đó. Một thuật toán mới dựa trên ý tưởng của nhóm tác giả An, Giang, Phú và Polthier, trong đó tiếp tục sử dụng kỹ thuật “Phễu” tương tự trong 2 chiều, tìm đường đi ngắn nhất giữa hai điểm trong một dãy các mặt của khối đa diện trong không gian 3 chiều, được trình bày. |
