NGHIÊN CỨU VÀ PHÂN TÍCH MỘT SỐ BÀI TOÁN HÌNH HỌC ỨNG DỤNG THUẬT TOÁN TĂNG TRƯỞNG NGẪU NHIÊN

Từ khóa:
: thuật toán tăng trưởng ngẫu nhiên hình học độ phức tạp
Tóm tắt
Nghiên cứu tập trung vào phân tích quá trình hoạt động và hiệu suất một số bài toán hình học được xây dựng dựa trên thuật toán tăng trưởng ngẫu nhiên. Nhóm tác giả đề cập đến khái niệm tính đối ngẫu trong hình học, làm nền tảng cho các thuật toán hình học trong không gian ba chiều. Mục đích của việc nghiên cứu và phân tích các thuật toán này nhằm cải thiện hiệu quả xử lý các bài toán hình học phức tạp. Thuật toán tăng trưởng ngẫu nhiên không chỉ đơn giản, dễ hiểu mà còn có hiệu suất tính toán cao, phù hợp để ứng dụng trong các bài toán hình học thực tế. Kết quả cho thấy, thuật toán tăng trưởng ngẫu nhiên áp dụng cho các bài toán hình học với thời gian chạy trung bình là O(nlogn).
Tài liệu tham khảo
  1. [1] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars (2008), Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008.
  2. [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2009), Introduction to Algorithms, 3rd ed., MIT Press, 2009.
  3. [3] S. Fortune and C. J. Wylie (1984), The Power of Duality in Computational Geometry, Journal of Algorithms, vol. 5, no. 3, pp. 287-303, 1984.
  4. [4] P. Bose and M. Smid (2019), On the average complexity of incremental convex hull algorithms in higher dimensions, Computational Geometry, vol. 82, pp. 101–111, 2019.
  5. [5] F. P. Preparata and M. I. Shamos (1985), Computational Geometry: An Introduction, Springer-Verlag, 1985.
  6. [6] M. de Berg and O. Cheong (2016), Computational Geometry in C: Modern Techniques and Applications, 4th ed., Springer, 2016.
  7. [7] O. Devillers and M. Teillaud (2020), Delaunay triangulation and randomized incremental algorithms, in Handbook of Discrete and Computational Geometry, CRC Press, 2020.
  8. [8] P. K. Agarwal and J. Erickson (2017), Geometric range searching and its relatives, ACM Computing Surveys, vol. 50, no. 4, pp. 1–56, 2017.
  9. [9] X. Li and Y. Chen (2021), Applications of convex hull algorithms in spatial data science, Journal of Spatial Information Science, vol. 23, pp. 1–25, 2021.