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 -