Applications of random sampling in computational geometry, II

Random sampling is used for several new geometric algorithms. The algorithms are “Las Vegas,” and their expected bounds are with respect to the random behavior of the algorithms. One algorithm reports all the intersecting pairs of a set of line segments in the plane, and requires Ο(A + n log n) expected time, where A is the size of the answer, the number of intersecting pairs reported. The algorithm requires Ο(n) space in the worst case. Another algorithm computes the convex hull of a point set in E3 in Ο(n log A) expected time, where n is the number of points and A is the number of points on the surface of the hull. A simple Las Vegas algorithm triangulates simple polygons in Ο(n log log n) expected time. Algorithms for half-space range reporting are also given. In addition, this paper gives asymptotically tight bounds for a combinatorial quantity of interest in discrete and computational geometry, related to halfspace partitions of point sets.