Về bao α - lõm ( α -Concave hulls), một mở rộng của bao lồi trong mặt phẳng
Báo cáo viên: Nguyễn Hữu Hiếu

Thời gian: 9h00, Thứ 4 ngày 13/11/2019
Địa điểm: Phòng 302 Nhà A5, Viện Toán học
Tóm tắt: Trong báo cáo này, chúng tôi trình bày về một mở rộng của bao lồi trong mặt phẳng, gọi là bao α - lõm. Chúng tôi trình bày chứng minh, bài toán tính α - đa giác với diện tích cho trước và bài toán tính bao α - lõm của tập hữu hạn điểm trong mặt phẳng là NP-complete (NP-đầy đủ), bằng cách đưa ra thuật toán quy dẫn từ một bài toán NP-đầy đủ đã biết. Nội dung báo cáo là một phần của bài báo: S. Asaeedi, F. Didehvar, A. Mohades (2017), α-Concave hull, a generalization of convex hull, Theoretical Computer Science, 702, 48-59.

Back