Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414623 | Computational Geometry | 2015 | 4 Pages |
Abstract
Let FF be a family of n axis-parallel boxes in RdRd and α∈(1−1/d,1]α∈(1−1/d,1] a real number. There exists a real number β(α)>0β(α)>0 such that if there are α(n2) intersecting pairs in FF, then FF contains an intersecting subfamily of size βn . A simple example shows that the above statement is best possible in the sense that if α≤1−1/dα≤1−1/d, then there may be no point in RdRd that belongs to more than d elements of FF.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
I. Bárány, F. Fodor, A. Martínez-Pérez, L. Montejano, D. Oliveros, A. Pór,