Convex hull for intersections of random lines
Daniel Berend, Vladimir Braverman
Abstract
The problem of finding the convex hull of the intersection points of random lines was studied in [dt] and [new], and algorithms with expected linear time were found. We improve the previous results of the model in [dt] by giving a universal algorithm for a wider range of distributions.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page