A deterministic view of random sampling and its use in geometry

B. Chazelle, J. Friedman

Research output: Contribution to journalArticlepeer-review

177 Scopus citations


The combination of divide-and-conquer and random sampling has proven very effective in the design of fast geometric algorithms. A flurry of efficient probabilistic algorithms have been recently discovered, based on this happy marriage. We show that all those algorithms can be derandomized with only polynomial overhead. In the process we establish results of independent interest concerning the covering of hypergraphs and we improve on various probabilistic bounds in geometric complexity. For example, given n hyperplanes in d-space and any integer r large enough, we show how to compute, in polynomial time, a simplicial packing of size O(rd) which covers d-space, each of whose simplices intersects O(n/r) hyperplanes.

Original languageEnglish (US)
Pages (from-to)229-249
Number of pages21
Issue number3
StatePublished - Sep 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Discrete Mathematics and Combinatorics


  • AMS subject classification (1980): 68C25, 52A22


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

Cite this