Tham khảo tài liệu 'thuật toán algorithms (phần 34)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | FINDING THE CONVEXHULL 323 why not just return the points on the hull in any order but output in the ordered form is obviously more useful and it has been shown that the unordered computation is no easier to do. For all of the algorithms that we consider it is convenient to do the computation in place the array used for the original point set is also used to hold the output. The algorithms simply rearrange the points in the original array so that the convex hull appears in the first positions in order. From the description above it may be clear that computing the convex hull is closely related to sorting. In fact a convex hull algorithm can be used to sort in the following way. Given N numbers to sort turn them into points in polar coordinates by treating the numbers as angles suitably normalized with a radius for each point. The convex hull of this point set is an N-gon containing all of the points. Now since the output must be ordered in the order the points appear on this polygon it can be used to find the sorted order of the original values remember that the input was unordered . This is not a formal proof that computing the convex hull is no easier than sorting because for example the cost of the trigonometric functions required to convert the original numbers to be sorted into points on the polygon must be considered. Comparing convex hull algorithms which involve trigonometric operations to sorting algorithms which involve comparisons between keys is a bit like comparing apples to oranges but it has been shown that any convex hull algorithm must require about N log N operations the same as sorting even though the operations allowed are likely to be quite different . It is helpful to view finding the convex hull of a set of points as a kind of two-dimensional sort because frequent parallels to sorting algorithms arise in the study of algorithms for finding the convex hull. In fact the algorithms that we ll study show that finding the convex hull is no harder
