An Efficient Algorithm for Determining the Connected Orthogonal Convex Hulls
Báo cáo viên: Nguyễn Kiều Linh (Học viện Công nghệ Bưu chính Viễn thông)

Thời gian: 9h00 đến 11h00 sáng thứ 4 ngày 24/3/2021

Địa điểm: Phòng 302 nhà A5, Viện Toán học

Tóm tắt báo cáo: The Quickhull algorithm for finding the convex hull of a finite set of points was independently conducted by Eddy in 1977 and Bykat in 1978. Inspired by the idea of this algorithm, we present a new efficient algorithm for finding orthogonal extreme points of the connected orthogonal convex hull of a finite set of points that still keeps advantages of the quickhull algorithm. Consequently, our algorithm runs faster than the others (the algorithms introduced by Montuno and Fournier in 1982 and by An, Huyen and Le in 2020). We also show that the expected complexity of the algorithm is O(nlogn), where n is the number of points.

Back