Discussion on an O(n) Time Algorithm for the Convex Hull of a Planar Point Set
Liu Jin · Chinese Journal of Computers · 2002
Wang Zi Qiang et al presented a new algorithm for computing the convex hull of a planar point set in 1998, and claimed that the worst case time complexity of the algorithm is O(n ), which can lead to a linear time algorithm for sorting. This correspondence gives a different standpoint on the cost time analysis of the algorithm, and further make clear that the lower bound to these problems under algebraic decision tree model is still Ω(n log n ).