Convex Hulls and Voronoi Diagrams
Bernard Chazelle · Cambridge University Press eBooks · 2000
The reader looking here for working codes may be disappointed. The problem of how to compute the convex hull of n points in optimal time is viewed mostly through a theoretical lens. Optimality is understood here in a worst-case setting: Given n points in R d , the convex hull is a polytope with O ( n [ d /2] ) faces, and possibly as many as that. It is well known that computing the polytope entails sorting, so the complexity we are aiming for is O ( n log n + n + n [ d /2] ). To approach this complexity is reasonably easy, but to design an optimal deterministic algorithm is surprisingly challenging. In this chapter we do just that. The algorithm is to this day the most sophisticated example of derandomization in computational geometry. It is also the most unlikely, considering how hopeless its basic line of attack might seem at first. To overcome such odds, the whole kitchen sink of sampling technology developed in the previous chapters is called into action. Interestingly, sampling is used for two very different purposes: One is to provide a divide-and-conquer mechanism (as we've seen in Chapter 5), and the other is to evaluate complicated potential functions approximately very fast (as we've seen nowhere yet). No other (deterministic) algorithm has yet been found for computing convex hulls optimally. So, perhaps more than any other, this chapter shows how deep and uniquely powerful the discrepancy method is in the area of algorithm design.