Daniel Berend

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 lineswas 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.