Quicker than Quickhull

Tiêu đềQuicker than Quickhull
Loại công bốJournal Article
Năm xuất bản2014
Tác giảHoang, NDung, Linh, NKieu
Tạp chíVietnam Journal of Mathematics
Thể tích43
Tóm tắt

In this paper, we present some modifications of the Quickhull algorithm finding the convex hull of a finite set of planar points. The underlying ideas are to reduce the number of the fundamental operations of the Quickhull algorithm calculating orientation and to decrease the size of input data by preprocessing and separating the original problem into smaller problems. Our numerical experiments show that the modifications reduce the computation time of the original Quickhull algorithm by a factor of three on average.