Further applications of random sampling to computational geometry
Kenneth L. Clarkson · 1986
IntroductionThis paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry.One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer.This algorithm requires randomized O(s d+`) preprocessing time to build a search structure for an arrangement of s hyperplanes in d dimensions.The structure has a query time that is worst-case O(logs).(The bound holds for any fixed ~ > 0, with the constant factors dependent on d and ~.) Using point-plane duality, the algorithm may be used for answering halfspace range queries.Another algorithm finds random samples of simplices to determine the separation distance of two polytopes.The algorithm uses randomized O(n[ d/2j) time, where n is the total number of vertices of the two polytopes.This matches previous results [DK851 for the case d : 3 and extends them.Another algorithm samples points in the plane to determine their order k Voronoi diagram, and requires randomized O(sk)o(s ~) time for s points.This sharpens the bound O(sk 2 logs) for Lee's algorithm [Lee821, and O(s 2 logs + s(s -k) log2 s) for Chazelle and Edelsbrunner's algorithm ICE851.Finally, random sampling is used to show that any set of s points in E 3 has O(sk 2 log 9 s/(log log s) 6) distinct j-sets with j < k. (For S C E d, a set S' C S with IS'} =j is a j-set of S if there is a halfspace h + with S' = S fqh+.)This sharpens with respect to k the previous bound O(sk 5) [CP851.The proof of the bound given here is an instance of a "probabilistic method" IES741.