Tóm tắt Luận án Tiến sĩ: Một số thuật toán hữu hiệu giải bài toán trong hình học tính toán dựa trên phương pháp đường định hướng

Hình học tính toán, một nhánh quan trọng trong khoa học máy tính, đã phát triển mạnh mẽ từ những năm 1970, với nhiều ứng dụng thực tiễn trong các lĩnh vực như điều khiển rô-bốt, GIS, và đồ họa máy tính. Các bài toán nền tảng như xây dựng lưới tam giác Delaunay và tìm đường đi ngắn nhất trên bề mặt đa diện là trọng tâm của nhiều nghiên cứu. Tuy nhiên, các thuật toán tuần tự hiện có thường đòi hỏi thời gian tính toán lớn khi xử lý dữ liệu quy mô lớn, làm giảm hiệu quả. Đặc biệt, một số phương pháp giải quyết đường đi ngắn nhất gặp phải hạn chế như chồng lấn tam giác. Luận án này tập trung vào việc phát triển các thuật toán hữu hiệu, đặc biệt là các thuật toán song song, dựa trên phương pháp đường định hướng để giải quyết các bài toán này, nhằm nâng cao hiệu suất xử lý và khắc phục những hạn chế hiện có.

Nghiên cứu sinh, sinh viên sau đại học và các nhà khoa học trong lĩnh vực khoa học máy tính, hình học tính toán, thiết kế thuật toán, đồ họa máy tính và các ngành liên quan cần giải quyết các bài toán hình học trên tập dữ liệu lớn.

Luận án tiến sĩ này tập trung giải quyết những thách thức về hiệu suất trong hình học tính toán, đặc biệt là đối với các bài toán xây dựng lưới tam giác Delaunay và tìm đường đi ngắn nhất trên bề mặt đa diện. Công trình này xuất phát từ nhận định rằng các thuật toán tuần tự truyền thống thường không đáp ứng được yêu cầu về thời gian khi xử lý dữ liệu lớn, đồng thời các phương pháp hiện có cho bài toán đường đi ngắn nhất còn tồn tại những hạn chế như vấn đề chồng lấn khi lật phẳng chuỗi tam giác. Để khắc phục những vấn đề này, luận án đề xuất và phát triển các thuật toán song song tiên tiến, dựa trên nền tảng của phương pháp đường định hướng. Cấu trúc luận án được tổ chức rõ ràng, bắt đầu với tổng quan về bối cảnh nghiên cứu, định nghĩa các khái niệm cốt lõi như lưới tam giác Delaunay, khối đa diện, đường đi ngắn nhất, và giới thiệu chi tiết về phương pháp đường định hướng cùng các nguyên lý của tính toán song song. Cụ thể, luận án trình bày thuật toán OFC-DELAUNAYTRIANGULATION, một thuật toán hiệu quả để ghép nối hai lưới tam giác Delaunay liền kề bằng cách sử dụng các đường tròn định hướng. Ngoài ra, một phương pháp song song hóa thuật toán cây phễu được giới thiệu để tìm đường đi ngắn nhất trên bề mặt đa diện, kết hợp hài hòa với phương pháp đường định hướng. Các kết quả thực nghiệm cho thấy các thuật toán song song đề xuất đạt được sự tăng tốc đáng kể so với các thuật toán tuần tự trước đây, minh chứng cho tính hiệu quả và tiềm năng ứng dụng của chúng trong việc xử lý các bài toán hình học tính toán phức tạp với quy mô dữ liệu lớn.