首页|A fast and efficient algorithm for determining the connected orthogonal convex hulls
A fast and efficient algorithm for determining the connected orthogonal convex hulls
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
The Quickhull algorithm for determining 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 determining the connected orthogonal convex hull of a finite set of points through extreme points of the hull, 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(n log n), where n is the number of points. (C) 2022 Elsevier Inc. All rights reserved.
NSTL
Elsevier
