TY - GEN

T1 - Deterministic view of random sampling and its use in geometry

AU - Chazelle, Bernard

AU - Friedman, Joel

PY - 1988

Y1 - 1988

N2 - 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(rd) 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(nd) storage and polynomial preprocessing.

AB - 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(rd) 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(nd) storage and polynomial preprocessing.

UR - http://www.scopus.com/inward/record.url?scp=0024140065&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024140065&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0024140065

SN - 0818608773

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 539

EP - 549

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

ER -