5. Applications of Helly’s Theorem in Combinatorial Geometry 23 Counting measure. Suppose that there is a finite set X Rd of |X| = n points and μ(A) = |A X|/n is the proportion of the points in X contained in A. Integrable density. Suppose that there is an integrable function f : Rd −→ R such that f(x) 0 for all x Rd and such that Rd f(x) dx = 1, where dx is the Lebesgue measure. Let μ(A) = A f(x) dx for all (Borel) measurable sets A. With a hyperplane H = x : c, x = α we associate two open halfspaces H+ = x Rd : c, x α and H− = x Rd : c, x α and two closed halfspaces H+ = x Rd : c, x≥ α and H− = x Rd : c, x≤ α . Proposition. Let μ be a Borel probability measure on Rd. Then there exists a point y Rd, called a center point, such that for any closed halfspace H containing y one has μ(H ) 1 d + 1 . Proof. For a closed halfspace G Rd, let G = Rd \ G be the complementary open halfspace. Let S be the set of all closed halfspaces G such that μ (∼) G 1/(d + 1). We observe that for any d + 1 halfspaces G1,... , Gd+1 from S one has μ (∼ G1 . . . Gd+1 ) (d + 1) (d + 1) = 1 and hence G1 . . . Gd+1 = Rd, which implies that G1 . . . Gd+1 = ∅. Helly’s Theorem implies that any finite family {Gi} of halfspaces from S has a non-empty intersection. Let us choose a finite number of halfspaces G1,... , Gm Rd such that the intersection B = G1 . . . Gm is bounded and hence compact. Enlarging the halfspaces by translations, if necessary, we can ensure that G1,... , Gm are from S. Thus {B ∩G : G S} is a family of compact sets such that every finite subfamily has a non-empty intersection. Hence there is a point y which belongs to all halfspaces G S. If H is an open halfspace containing y, then the complementary closed halfspace does not contain y and hence does not belong to S. Then we must have μ(H ) 1/(d + 1). Since μ is σ-additive and a closed halfspace can be represented as an intersection of countably many nested open halfspaces, the result follows. The above result was first obtained in 1916 by J. Radon. The above proof belongs to I.M. Yaglom and V.G. Boltyanskii (1956).
Previous Page Next Page