A deterministic view of random sampling and its use in geometry

Abstract

A number of efficient probabilistic algorithms based on the combination of divide-and-conquer and random sampling have been recently discovered. It is shown that all those algorithms can be derandomized with only polynomial overhead. In the process. results of independent interest concerning the covering of hypergraphs are established, and various probabilistic bounds in geometry complexity are improved. For example, given n hyperplanes in d-space and any large enough integer r, it is shown how to compute, in polynomial time, a simplicial packing of size O(r/sup d/) that covers d-space, each of whose simplices intersects O(n/r) hyperplanes. It is also shown how to locate a point among n hyperplanes in d-space in O(log n) query time, using O(n/sup d/) storage and polynomial preprocessing.<>