Applications of Random Sampling inComputational Geometry, IIKenneth L. Clarkson and Peter W. ShorAT&T Bell Labor atoriesMurray Hill, New Jersey 079741989AbstractWe use random sampling for several new geometric algorithms. Thealgorithms are “Las Vegas,” and their expected bounds are with respectto the random behavior of the algorithms. These algorithms follow fromnew general results giving sharp bounds for the use of random subsets ingeometric algorithms. These bounds show that random subsets can beused optimally for divide-and-conquer, and also give bounds for a simple,general technique for building geometric structures incrementally. Onenew algorithm reports all the intersecting pairs of a set of line segmentsin the plane, and requires O(A + n log n) expected time, where A is thenumber of intersecting pairs reported. The algorithm requires O(n) spacein the worst case. Another algorithm computes the convex hull of n pointsin Edin O(n log n) expected time for d = 3, and O(n!d/2") expected timefor d > 3. The algorithm also gives fast expected times for random inpu tpoints. Another algorithm computes th e diameter of a set of n points inE3in O(n log n) expected time, and on the way computes the intersectionof n unit balls in E3. We show that O(n log A) expected time sufficesto compute the convex hull of n points in E3, where A is the number ofinput points on the surface of the hull. Algorithms for halfspace rangereporting are also given. In addition, we give asymptotically tight boundsfor (≤k)-sets, which are certain halfspace partitions of point sets, and givea simple proof of Lee’s bounds for high order Voronoi diagrams.1 IntroductionIn recent years, random sampling has seen increasing use in discrete and com-putational geometr y, with applications in proximity problems, point location,and range queries [11, 12, 28]. These applications have largely used randomsampling for divide-and-conquer, to split problems into subproblems each guar-anteed to be small. In this pa per, we use random s ampling in a similar way,with the additional observation that the total of the sizes of the s ubproblems is1small on the average. This fac t gives improved resource bounds for a variety ofrandomized algorithms.A key application of this shar per average-ca se bound is a general result im-plying that a simple, general technique for co mputing geometric structures yieldsasymptotically optimal algorithms fo r several fundamental problems. This methodis a small change to one of the simplest ways of building a geometric structure,the incremental approach: for exa mple, for determining the intersection of a setof halfspaces, this approach adds the halfspaces one by one and maintains theresulting intersections.Such an incremental appro ach gives an optimal algorithm for constr uctingan arrangement of hyperplanes[23]. In general, we have a set of objects, notnecessarily ha lfspaces or hyper planes, that determine a structure, and we addthe objects one by one, maintaining the resulting structure. One variant ofthis incremental approach, a simple way to randomize the process, is to a ddthe objects in random order. Chew[10] used this approach for building Voronoidiagrams of the vertices of convex polygons. In this paper, we prove a generaltheorem regarding a version of this randomized and incremental technique. Weshould note that although our technique is incremental, it is not on-line, as somesimple information is maintained for the objects that are not yet added.Some general terminology and assumptions: in this paper, the dimension dis generally considered to be fixed. The expected resource bounds shown are“Las Vegas,” and the expec tations are with respect to the random behaviorof the algorithms, unless otherwise indica ted. The parameter A is generallyused to denote the size of the Answer to a computation. The inputs to thealgorithms will be assumed nondeg e nerate, so an input set of line seg ments hasno three intersecting at the same po int, an input set of points in Edhas nod + 1 coplanar, and so on. This is no great loss of generality, as usually smalltie-breaking perturbatio ns can be appropriately applied, and the answer sizes Aas defined are unchanged. Recently systematic methods have b een develope d toapply such perturbations “formally,” that is, to break ties in an a rbitrary butconsistent way, so a s to simulate nondegeneracy with degenerate input [22, 44].1.1 Problems, results, and r elated workThis pape r is a combination of the two papers[14] and [16], with a sharperproof of the main divide-and-conquer theorem (here Theorem 3.6). The resultscan be viewed as an improvement to those of [12], and this fact s uggested thetitle of this paper. The results in this paper have been used in an algorithmfor triangulating simple po lygons[17], for small-dimensional linear and integerprogramming[13], for an optimal parallel algorithm for Voronoi diagrams[39],and in vario us combinatorial results on arrangements[15].Algorithms for trapezoidal diagrams and line segment intersec-tions. For S a set of n line segments in the plane, what are the pairs ofintersecting segments of S? This computational problem has received muchattention, culminating in the recent algorithm of Chazelle and Edelsbrunnerrequiring O(A + n log n) time in the worst case to report the A intersecting2pairs [5]. Their algorithm requires (moderately) sophisticated data structuresand many sophisticated algorithmic techniques, and Ω(n + A) space. This pa-per gives three Las Vegas algorithms for this problem. Two of the algorithmsincrementally build the trapezoidal diagram of S (defined below), adding linesegments in random order. As a byproduct, the intersecting pairs of S arefound. The algorithms require O(A + n log n) expected time; one requir e s ex-pected O(A + n log n) space, and the other requires O(n + A) space in the worstcase. Mulmuley [35] has independently found a similar algorithm, with the sametime bound and O(n + A) worst-case space bound. Another algorithm givenhere builds on these algorithms, and requires the same time but O(n) spacein the worst case. Reif and Sen [38] applied randomization to obtain parallelalgorithms for related problems.The trapezoidal diagram (or “vertical visibility map”), denoted T (S), isdefined as follows: for every point p that is either an e ndpoint of a segmentin S, or an intersection point of two segments in S, extend a vertical segmentfrom p to the first segment of S ab ove