A linear algorithm for computing convex hulls for random lines Academic Article uri icon


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

publication date

  • January 1, 2009