Article ID Journal Published Year Pages File Type
414623 Computational Geometry 2015 4 Pages PDF
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
, , , , , ,