Mục tiêu nghiên cứu của luận án là đề xuất thuật toán Quickhull tìm bao lồi cho tập hữu hạn các hình tròn đồng thời chứng minh sự đúng đắn của thuật toán, tính độ phức tạp của thuật toán trong trường hợp xấu nhất, trung bình và theo nghĩa smoothed analysis. Các thử nghiệm số để minh họa thuật toán cũng được trình bày ở nội dung này. | ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN o0o Nguyễn Kiều Linh BÀI TOÁN TÌM BAO LỒI CỦA TẬP ĐIỂM HỮU HẠN VÀ ỨNG DỤNG Chuyên ngành Toán ứng dụng Mã số 62 46 01 12 DỰ THẢO TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2018 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - ĐẠI HỌC QUỐC GIA HÀ NỘI Tập thể hướng dẫn khoa học HD1 TS. HOÀNG NAM DŨNG HD2 PGS. TS. PHAN THÀNH AN Phản biện . Phản biện . Phản biện . Luận án sẽ được bảo vệ trước Hội đồng cấp Đại học Quốc gia chấm luận án tiến sĩ họp tại TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - ĐẠI HỌC QUỐC GIA HÀ NỘI Vào hồi . . . giờ . . . ngày . . . tháng . . . năm 20. Có thể tìm hiểu luận án tại - Thư viện Quốc gia Việt Nam - Trung tâm Thông tin - Thư viện Đại học Quốc gia Hà Nội. 1 Mở đầu Bài toán tìm bao lồi của tập hữu hạn điểm là một trong những bài toán đặc biệt quan trọng trong lĩnh vực hình học tính toán bởi các ứng dụng đa dạng của nó chẳng hạn như đồ họa máy tính nhận dạng mẫu xử lý hình ảnh tìm đường đi ngắn nhất cho robot số liệu thống kê . . . Hơn nữa bài toán tìm bao lồi thường được sử dụng như một bài toán phụ một bước tiền xử lý quan trọng trong các bài toán hình học khác như tìm tam giác phân Delaunay tính biểu đồ Voronoi tìm đường kính của một tập hợp tìm các lớp lồi của một tập hợp tìm đường đi ngắn nhất . . . Các ứng dụng quan trọng cũng như các ý nghĩa thực tiễn của bài toán tìm bao lồi đã thu hút được rất nhiều nhà khoa học nghiên cứu và đưa ra các thuật toán giải bài toán này. Điển hình như sự phát hiện của D. R. Chand và S. S. Kapur vào năm 1970 và R. A. Jarvis vào năm 1973 với thuật toán gói quà gift-wrapping R. Graham vào năm 1972 với thuật toán quét Graham Graham scan W. Eddy năm 1977 và A. Bykat năm 1978 với thuật toán Quickhull F. P. Preparata và S. J. Hong năm 1977 với thuật toán chia để trị devide-and-conquer M. Kallay năm 1984 với thuật toán tăng dần incremental T. Chan vào năm 1993 với thuật toán Chan . . . Hiện nay có rất nhiều đề xuất cải tiến để tăng tốc cho .
