A linear algorithm for computing convex hulls for random lines
Daniel Berend, Vladimir Braverman · ACM Transactions on Algorithms · 2009
Finding the convex hull of n points in the plane requires O ( n log n ) time in general. In Devroye and Toussaint [1993] and Golin et al. [2002] the problem of computing the convex hull of the intersection points of n lines was considered, where the lines are chosen randomly according to two various models. In both models, linear-time algorithms were developed. Here we improve the results of Devroye and Toussaint [1993] by giving a universal algorithm for a wider range of distributions.