1. Họ và tên nghiên cứu sinh: Nguyễn Kiều Linh
2. Giới tính: Nữ
3. Ngày sinh: 21/09/1985
4. Nơi sinh: Yên Bái
5. Quyết định công nhận nghiên cứu sinh: 4982 /QĐ-ĐHKHTN ngày 27/11/2013 của Hiệu trưởng Trường Đại học Khoa học Tự nhiên.
6. Các thay đổi trong quá trình đào tạo:
- Quyết định số 2506/QĐ-ĐHKHTN ngày 25/7/2017 của Hiệu trưởng Trường Đại học Khoa học Tự nhiên về việc tạm ngừng học tập.
- Quyết định số 401/QĐ-ĐHKHTN ngày 27/02/2017 của Hiệu trưởng Trường Đại học Khoa học Tự nhiên về việc tiếp tục thời gian học tập và nghiên cứu tại Trường
- Quyết định số 1418/QĐ-ĐHKHTN ngày 09/5/2018 của Hiệu trưởng Trường Đại học Khoa học Tự nhiên về việc gia hạn đào tạo và bảo vệ luận án cho nghiên cứu sinh đến ngày 31/12/2018.
7. Tên đề tài luận án: Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn.
8. Chuyên ngành: Toán ứng dụng
9. Mã số:6246 0112
10. Cán bộ hướng dẫn khoa học: Hướng dẫn chính: TS. Hoàng Nam Dũng
Hướng dẫn phụ: PGS.TS Phan Thành An
11. Tóm tắt các kết quả mới của luận án:
Luận án trình bày một số vấn đề liên quan đến bài toán tìm bao lồi của tập hữu hạn điểm và tập hữu hạn các hình tròn đạt được các kết quả chính như sau.
· Đề xuất được một số kỹ thuật để tăng tốc cho thuật toán Quickhull 2D. Các tính toán chỉ ra thuật toán áp dụng các kỹ thuật này tăng tốc khá hiệu quả, tăng khoảng 3 lần so với phiên bản hiện có.
· Giới thiệu một kỹ thuật giới hạn không gian tìm kiếm để cải tiến thủ tục tìm một mặt của bao lồi qua một mặt con cho trước áp dụng cho thuật toán gói quà tìm bao lồi của tập điểm hữu hạn trong Rd. Một số thử nghiệm tính toán đã chỉ ra rằng thuật toán áp dụng kỹ thuật này giảm được khoảng 40% so với thuật toán gói quà ban đầu và khoảng 35% so với một phiên bản cải tiến thuật toán này năm 2013.
· Đề xuất thuật toán Quickhull tìm bao lồi của tập hữu hạn các hình tròn trong mặt phẳng dựa vào ý tưởng của thuật toán Quickhull tính bao lồi cho bộ điểm. Các chứng minh sự đúng đắn của thuật toán và tính độ phức tạp tính toán trong trường hợp xấu nhất, trung bình và theo nghĩa smoothed analysis cũng được trình bày một cách chi tiết. Các tính toán của chúng tôi chỉ ra rằng thuật toán Quickhull chạy nhanh hơn gấp khoảng 3,8 lần so với thuật toán tăng dần.
· Trình bày một phương pháp giải một bài toán tìm vị trí tối ưu: tìm một điểm x trong một tập D lồi đóng cho trước sao cho khoảng cách Euclide xa nhất từ x tới các điểm của tập hữu hạn C là ngắn nhất. Phương pháp được áp dụng là một thuật toán dưới vi phân (subgradient algorithm) để giải quyết bài toán tối ưu không trơn. Chúng tôi đề xuất một bước tiền xử lý quan trọng là tìm đỉnh của bao lồi của C trước khi giải bài toán xác định vị trí tối ưu. Một số kết quả tính toán thực nghiệm của chúng tôi đã chỉ ra rằng, việc tính bao lồi trước khi thực hiện bài toán là hiệu quả.
· Một đề xuất khác để tăng tốc cho thuật toán tìm bao lồi dưới cho lớp bài toán ứng dụng tìm tam giác phân Deulaunay và biểu đồ Voronoi cũng được đề xuất. Các kết quả tính toán chỉ ra rằng thuật toán cải tiến là nhanh hơn khoảng 1,8 lần so với một thuật toán khác đề xuất năm 2015.
12. Khả năng ứng dụng thực tiễn: Xử lý hình ảnh, hệ thống thông tin GIS, tìm đường đi ngắn nhất, …
13. Các hướng nghiên cứu tiếp theo: Nghiên cứu bài toán tìm bao lồi của tập hình elippse, tập các đoạn thẳng, đa giác lồi, đa diện lồi, hình cầu, …
14. Các công trình công bố liên quan đến luận án:
[1] N. D. Hoang and N. K. Linh (2015), “Quicker than quickhull”, Vietnam Journal of Mathematics, 43, pp. 57-70.
[2] N. K. Linh and L. D. Muu (2015), “A convex hull algorithm for solving a location problem”, RAIRO-Operations Research, 49, pp. 589-600.
a[3] N. K. Linh, C. Song, P. T. An, N. D. Hoang, D.-S. Kim (2018), “QHullDisk: A Faster Convex Hull Algorithm for Disks”, Submitted to ACM Transactions on Mathematical Software (TOMS).
