Deterministic view of random sampling and its use in geometry

Bernard Chazelle, Joel Friedman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

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 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 d) storage and polynomial preprocessing.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages539-549
Number of pages11
ISBN (Print)0818608773
StatePublished - Dec 1 1988

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Deterministic view of random sampling and its use in geometry'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Friedman, J. (1988). Deterministic view of random sampling and its use in geometry. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 539-549). Publ by IEEE.