Piercing random boxes |
| |
Authors: | Linh V. Tran |
| |
Affiliation: | Department of Mathematics, Rutgers, Piscataway, New Jersey 08854 |
| |
Abstract: | Consider a set of n random axis parallel boxes in the unit hypercube in ${bf R}^{d}$ , where d is fixed and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least $Omega_d(sqrt{n}(log n)^{d/2-1})$ and at most $O_d(sqrt{n}(log n)^{d/2-1}log log n)$ . © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 365–380, 2011 |
| |
Keywords: | random boxes random hypergraph discrepancy |
|
|