DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional