Piercing random boxes |
| |
Authors: | Linh V Tran |
| |
Institution: | 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 |
|
|