Applications of random sampling in computational geometry. II (Q1823685): Difference between revisions

The paper is an excellent overview about several ``Las Vegas''-algorithms given by the authors. Some results are improvements of results given by the first author in an earlier paper \textit{K.L. Clarkson} [Discrete Comput. Geom. 2, 195-222 (1987; Zbl 0615.68037)]. Random sampling is used for several new geometric algorithms. The central lemma formulated at the beginning gives sharp bounds for the use of random subsets. Such subsets can be used for divide and conquer and for some incremental techniques. Some interesting results and algorithms are the following: An 0(A \(+\) n log n)-expected time and 0(n)-space-algorithm reports all the A intersecting pairs of a set of n line segments in the plane. An 0(n log n)-expected time algorithm computes the convex hull of n points in \(E^ 3\) (for \(d>3:\) \(0(n^{\lfloor d/2\rfloor}))\). An 0(n log n)-expected time algorithm computes the diameter of a set of n points in \(E^ 3\). Algorithms for halfspace range reporting and a simple proof for bounds on high-order Voronoi diagrams are given. In the concluding remarks relations with deterministic algorithms and possible extensions are discussed.