TRANG THÔNG TIN LUẬN ÁN TIẾN SĨ
Tên đề tài luận án: “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”.
Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01
Họ và tên nghiên cứu sinh: Trịnh Minh Đức
Người hướng dẫn khoa học:
Hướng dẫn 1: TS. Đặng Thị Oanh
Hướng dẫn 2: PGS.TS Phan Thành An
Đơn vị đào tạo: Trường Đại học Công nghệ thông tin và Truyền thông, Đại học Thái Nguyên
1. Mục tiêu nghiên cứu của luận án
Mục tiêu của luận án là nghiên cứu đề xuất một số thuật toán 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.
Mục tiêu nghiên cứu cụ thể của luận án như sau:
- Nghiên cứu phương pháp đường định hướng để giải bài toán xây dựng lưới tam giác Delaunay của một tập hợp điểm phẳng.
- Nghiên cứu phương pháp đường định hướng để tìm các phễu con của một phễu.
- Nghiên cứu thuật toán cây phễu và tiến hành song song hóa thuật toán cây phễu để tìm đường đi ngắn nhất từ một điểm nguồn cố định đến tất cả các đỉnh trên một bề mặt đa diện.
2. Phương pháp nghiên cứu
Phương pháp nghiên cứu lý thuyết: Tổng hợp và nghiên cứu các tài liệu liên quan đến phương pháp đường định hướng, bài toán xây dựng lưới tam giác Delaunay và bài toán tính chính xác các đường đi ngắn nhất từ một điểm nguồn cố định đến tất cả các đỉnh trên một bề mặt đa diện. Tìm hiểu các hướng nghiên cứu mới liên quan đến hai bài toán này và đề xuất phương pháp cải tiến.
Phương pháp nghiên cứu thực tiễn: Thực hiện việc cài đặt thử nghiệm các thuật toán với các bộ dữ liệu khác nhau cùng các chỉ số đánh giá để khẳng định tính hiệu quả của các thuật toán và giải pháp được đề xuất.
3. Kết luận và hướng phát triển
3.1. Kết luận
Luận án nghiên cứu phương pháp đường định hướng để giải một số bài toán trong hình học tính toán, các kết quả luận án đạt được:
- Đưa ra một miền giới hạn để làm giảm số điểm cần kiểm tra trong việc xác định một đường tròn định hướng. Từ đó đề xuất một thuật toán mới để ghép nối hai lưới tam giác Delaunay sử dụng phương pháp đường tròn cuối và đường tròn định hướng. Đề xuất một lược đồ song song hóa để ghép nối hai lưới tam giác Delaunay.
- Đề xuất hai phương pháp song song hóa thuật toán cây phễu để tìm đường đi ngắn nhất trên bề mặt đa diện. Đề xuất một lược đồ song song hóa tìm đường đi ngắn nhất từ một đỉnh nguồn đến đích trực tiếp của nó trong vùng xử lý trong không gian ba chiều. Đề xuất phương pháp đường định hướng để tìm các con của phễu. Phương pháp này mang lại một cách tiếp cận mới để xác định các con của một phễu.
- Các kết quả thực nghiệm đã chỉ ra tính hiệu quả của các phương pháp được đề xuất. Nó cho thấy khả năng ứng dụng hiệu quả của phương pháp đường định hướng vào các bài toán thực tế.
3.2. Hướng phát triển của luận án
- Nghiên cứu cải tiến thuật toán OFC-DelaunayTriangulation, nghiên cứu để có thể song song hóa thuật toán OFC-DelaunayTriangulation, qua đó nâng cao hiệu suất và làm giảm thời gian tính toán.
- Nghiên cứu cải tiến thuật toán cây phễu để tìm tất cả các đường ngắn nhất từ một điểm nguồn s đến tất cả các đỉnh trên bề mặt một đa diện lồi trong thời gian O(n log n) với không gian O(n).
- Chứng minh tính đúng đắn các lược đồ song song trong chương 2 và chương 3, thực thi các thuật toán song song tương ứng và so sánh với một số thuật toán song song đã biết.
THE ABSTRACT OF DOTORAL THESIS
Thesis title: "Some efficient algorithms for solving computational geometry problems based on method of orienting curves"
The author’s name: Trinh Minh Duc
Supervisors:
1. Dr. Dang Thi Oanh
2. Assoc. Prof. Phan Thanh An
Major: Computer Science Code: 9480101
The name of postgraduate training institution: University of Information and Communication Technology, Thai Nguyen University
1. Thesis purpose and objectives
The objectives of this thesis is to propose and study several algorithms for solving problems in computational geometry based on method of orienting curves.
The specific research objectives of the thesis are as follows:
- To study the method of orienting curves for constructing the Delaunay triangulation of a set of planar points.
- To study the method of orienting curves for identifying the children of a funnel.
- To study the funnel tree algorithm and parallelize it to find the shortest paths from a fixed source point to all vertices on a polyhedral surface.
2. Research methods
Theoretical research method: Synthesize and study documents related to the method of orienting curves, the problem of constructing Delaunay triangulations, and the problem of accurately computing the shortest paths from a fixed source point to all vertices on a polyhedral surface. Explore new research directions related to these two problems and propose improved methods.
Practical research method: Implement experimental versions of the algorithms using different datasets and evaluation metrics to validate the effectiveness of the proposed algorithms and solutions.
3. Conclusions
3.1. Conclusions
This thesis studies the Method of Orienting Curves for solving various problems in computational geometry. The main contributions of the dissertation are:
- Proposing a restricted region to reduce the number of points required for checking an orienting circle. Based on this, a new algorithm is introduced for merging two Delaunay triangulations using the final circle and orienting circle method. A parallelization scheme for merging two Delaunay triangulations is also proposed.
- Proposing two parallelization methods for the funnel tree algorithm to compute the shortest paths on a polyhedral surface. Additionally, a parallelization scheme for computing the shortest path from a source vertex to its direct destination within a processing region in three-dimensional space is proposed.
- Proposing the Method of Orienting Curves to identify the children of a funnel. This approach provides a novel method for determining the children of a funnel.
- Experimental results demonstrate the effectiveness of the proposed methods, highlighting the applicability of the Method of Orienting Curves to real-world problems.
3.2. Future research directions
- Enhancing the OFC-DelaunayTriangulation algorithm and investigating its parallelization to improve efficiency and reduce computation time.
- Improving the funnel tree algorithm to compute all shortest paths from a source point s to all vertices on a convex polyhedral surface in O(n log n) time using O(n) space.
- Proving the correctness of the parallelization schemes in Chapters 2 and 3, implementing the corresponding parallel algorithms, and comparing them with existing parallel algorithms.
