Combinatorics, Probability and Computing

Table of Contents - 2003 - Volume 12, Issue 02  


The Clarkson–Shor Technique Revisited and Extended

MICHA SHARIR a1 1
a1 School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: sharir@cs.tau.ac.il)

Abstract

We provide an alternative, simpler and more general derivation of the Clarkson–Shor probabilistic technique [7] and use it to obtain several extensions and new combinatorial bounds.

(Received October 18 2001)
(Revised September 26 2002)


Footnotes

1 Work on this paper was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the US–Israeli Binational Science Foundation, by a grant from the Israeli Academy of Sciences Center of Excellence program in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.