Abstract
We give a simple algorithmic technique for building geometric structures. The technique is randomized and incremental. As an application, we give an algorithm of this kind for computing the intersection of a set of halfspaces in three dimensions. (This intersection problem is linear-time equivalent to the computation of the convex hull of a point set.) The algorithm requires &Ogr;(n log n) expected time, where the expectation is over the random behavior of the algorithm. A similar algorithm can be used to determine the intersection of a set of unit balls in E3, the problem of spherical intersection. This problem arises in the computation of the diameter of a point set in E3. For a set S of n points, the diameter of S is the greatest distance between two points in S. We give a randomized reduction from the problem of determining the diameter to the problem of computing spherical intersections, resulting in a Las Vegas algorithm for the diameter requiring &Ogr;(n log n) expected time. The best algorithms previously known for this problem have worst-case time bounds no better than &Ogr;(n √n log n) [Agg].