Convex Hulls for Random Lines

Consider n i.i.d. random lines in the plane defined by their slope and distance from the origin. The slope is uniformly distributed on [0, 2π] and independent of the distance R from the origin. These lines define a set I of n(n - 1)/2 intersection points. It was recently shown by Atallah and Ching and Lee that the cardinality of the convex hull of these intersection points is O(n), and they exhibited an O(n log n) time algorithm for computing such a convex hull. Let N_ch and N_ol be the number of points on the convex hull and outer layer of I, respectively. We show that there exist arrangements of lines in which N_ol = n(n - l)/2. We show that, nevertheless, both N_ch and N_ol have expected values O(1), and give bounds that are uniform over all distributions of R with 0 ≤ ER < ∞. These results lead to an algorithm for computing the convex hull of I in O(n log n) worst-case time and O(n) expected time under these conditions.