Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 37 (1996), No. 1, 67-74.

(n+1)–Families of Sets in General Position

Mircea Balaj

Department of Mathematics, Oradea University Str. Armatei Române Nr. 5, 3700 Oradea, Romania

Abstract. A family of sets in R^{n} is said to be in general position if any m–flat, 0 ≤ m ≤ n − 1, intersects at most m + 1 members of the family. Using the Fan– Glicksberg–Kakutani fixed point theorem, we prove that if {A_{1}, A_{2}, …, A_{n+1}} is a family of compact convexly connected sets then for any proper subset I of {1, 2, …, n+1}, there exists exactly one hyperplane H which separates strictly the sets ∪{A_{i} : i ∈ I} and ∪{A_{j} : j ∈ {1, 2, ⋯, n + 1} \ I} and satisfies d(A_{1}, H) = d(A_{2}, H) = ⋯ = d(A_{n+1}, H). MSC 1991: 52A20, 52A37

1. Introduction

Denote by R^{n}, the real n-dimensional Euclidean space, and by ∥·∥, the norm in this space. If A is a compact set and H is a hyperplane in R^{n}, we set d(A, H) = min{∥x − y∥ : x ∈ A, y ∈ H}. The standard abbreviations aff A, conv A, card A are used to define the affine hull, convex hull and cardinality of A. For every subset I of \{1, 2, …, n + 1\}, \overline{I} denotes the complement of I in {1, 2, …, n + 1}. If H = {x ∈ R^{n} :< x, b >= λ} is a hyperplane, the corresponding halfspaces {x ∈ R^{n} :< x, b > < λ}, {x ∈ R^{n} :< x, b > ≤ λ}, {x ∈ R^{n} :< x, b > > λ}, {x ∈ R^{n} :< x, b > ≥ λ}, are denoted respectively by H^{<}, H^{≤}, H^{>}, H^{≥}.

Definition 1. A family A of sets in R^{n}is said to be in general position if any m-flat, 0 ≤ m ≤ n − 1, intersects at most m + 1 members of A.

A family of sets in general position is called in [8], [9] an independent family, and in [1] and [4] a separated family.

Remark. Let m = min{n + 1, card A}. It is easy to see that the family A is in general position if and only if for every choice of sets A_{1}, A_{2}, …, A_{m} ∈ A and every choice of points a_{1} ∈ A_{1}, a_{2} ∈ A_{2}, …, a_{m} ∈ A_{m}, the set {a_{1}, a_{2}, …, a_{m}} is affinely independent.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1996 Heldermann Verlag, Berlin Definition 2. A set A is called convexly connected if there is no hyperplane H such that H ∩ A = ∅ and A contains points in both the open halfspaces determined by H. (cf. [5] and [13], p.174)

2. A characterization of (n+1)-families of convexly connected sets in general position

Let us begin by recalling two types of separation of two sets (see [6]). Let A and B be to sets in a vector space separated by a hyperplane H. We say that the sets A and B are nicely separated by H if the separating hyperplane H is disjoint from A or from B. The sets A and B are strongly separated by H if the separating hyperplane is at positive distance from both A and B.

Theorem 1. Let A be a (n+1)-family of convexly connected sets in R^{n}. Then the following assertions are equivalent:

(i) A is in general position.

(ii) For any hyperplane H, there exist two members of A which are nicely separated by a translate of H.

Proof. (i) implies (ii). Let H be a hyperplane in R^{n} and b ≠ 0 be a normal vector to H. We define a continuous function f : R^{n} → R, f(x) =< x, b > . Since each A ∈ A is convexly connected, f(A) is an interval and hence, a convex set in R.

We claim that there exist two members A_{1}, A_{2} of A such that f(A_{1}) ∩ f(A_{2})= ∅. Otherwise, it follows by Helly’s theorem that there exists an element λ ∈ ∩{f(A) : A ∈ A} and the hyperplane {x ∈ R^{n} :< x, b >= λ} intersects all members of A. But this contradicts (i).

Choosing a convenient sense for the vector b, it follows that

(1)  < x, b > < < y, b > for every x ∈ A_{1} and y ∈ A_{2}

and

(2)  sup{< x, b >: x ∈ A_{1}} ≤ inf{< y, b >: y ∈ A_{2}};

that is, the sets A_{1} and A_{2} are separated by a translate of H. The relation (1) implies that A_{1} and A_{2} are in fact nicely separated.

(ii) implies (i). By way of contradiction, suppose that there exists a hyperplane H = {x ∈ R^{n} :< x, b >= λ} which intersects all members of A. From the hypothesis, there exists two members A_{1} and A_{2} of A nicely separated by a translate of H. If x ∈ A_{1} ∩ H and y ∈ A_{2} ∩ H then we obtain the contradiction

λ =< x, b > < < y, b >= λ.

Corollary 2. Let A be a (n + 1)-family of compact convexly connected sets in R^{n}. Then the following assertions are equivalent:

(i) A is in general position.

(ii) For any hyperplane H, there exist two members of A which are strongly separated by a translate of H.

Proof. (i) implies (ii). Since the sets A_{i} ∈ A are compact, the infimum and the supremum in (2) are attained values and from (1), we deduce that A_{1} and A_{2} are strongly separated by H.

Since the strong separation implies the nice separation, the implication (ii) → (i) follows from the similar implication in Theorem 1.

3. Equally spaced hyperplanes for (n+1)-families of compact sets

In our proof of Theorem 5 the following result is crucial:

Lemma 3. Let [x_{1}, x_{2}, …, x_{n+1}] be an n-simplex in R^{n}. Then

(i) for each proper subset I of {1, 2, …, n + 1} there exists exactly one hyperplane H such that

(3)  the sets \{x_{i} : i ∈ I\} and \{x_{j} : j ∈ \overline{I}\} are strictly separated by H, and

(4)  d(x_{1}, H) = d(x_{2}, H) = ⋯ = d(x_{n+1}, H).

(ii) There exist exactly 2^{n} − 1 hyperplanes H which satisfy (4).

Proof. (i) For the sake of simplicity, let I = {1, 2, …, k}, with 1 ≤ k ≤ n. The distance from an arbitrary point x_{0} to a hyperplane

(5)  H = {x ∈ R^{n} :< x, b >= λ}

is given by the Ascoli formula (see [11] p.91)

(6)  d(x_{0}, H) = \frac{| < x_{0}, b > −λ|}{∥b∥}

Since the pair (b, λ) ∈ (R^{n}\{0})×R for which the hyperplane H admits the representation (5) is uniquely determined apart from a multiplicative constant, the conditions (3) and (4) are equivalent with the conditions

(7)  \{ \begin{matrix}< x_{1}, b > −λ & = ⋯ = & < x_{k}, b > −λ & = & 1 \\ < x_{k+1}, b > −λ & = ⋯ = & < x_{n+1}, b > −λ & = & −1 \end{matrix}

Denoting by (x_{i1}, x_{i2}, …, x_{in}) the coordinates of x_{i}, 1 ≤ i ≤ n + 1, and by (b_{1}, b_{2}, …, b_{n}) the coordinates of b, we are lead to an (n + 1) × (n + 1) linear system

(8)  x_{i1}b_{1} + x_{i2}b_{2} + ⋯ + x_{in}b_{n} − λ = ε_{i}, 1 ≤ i ≤ n + 1,

where

ε_{i} = \{ \begin{matrix}1 & if & 1 ≤ i ≤ k \\ −1 & if & k + 1 ≤ i ≤ n + 1. \end{matrix}

From the afine independence of the points x_{1}, x_{2}, …, x_{n+1}, it follows that the determinant D of order n + 1 having the general row (x_{i1}, x_{i2}, …, x_{in}, 1) is different from zero. This proves that the system (8) possesses the unique solution

(9)  \{ \begin{matrix}b_{j} & = & −\frac{D_{j}}{D} , & 1 ≤ j ≤ n \\ λ & = & −\frac{D_{n+1}}{D} \end{matrix}

where D_{j} is the determinant of order n + 1 having the general row (x_{i1}, x_{i2}, …, x_{i,j−1}, ε_{i}, x_{i j+1}, …, x_{in}, 1) and D_{n+1} is the determinant of the same order, with the general row (x_{i1}, …, x_{in}, ε_{i}). This shows that there exists a unique hyperplane H which satisfies the conditions (3) and (4). Note that d(x_{i}, H) = \frac{1}{∥b∥}, 1 ≤ i ≤ n + 1 and that the points x_{i}, i ∈ I, lie in the open halfspace H^{>}, while the points x_{j}, j ∈ \overline{I} lie in H^{<}.

Obviously, if H is a hyperplane equally spaced from the vertices of a simplex then these vertices can not be all situated in the same part of H. The assertion (ii) follows now from (i).

Let X and Y be two topological spaces. Denote by 2^{Y} the family of all subsets of Y. A map f : X → 2^{Y} is said to be upper semicontinous if f^{−1}(F) = {x ∈ X : f(x) ∩ F ≠ ∅} is closed in X for any closed subset F of Y. The following result can be found in [12], p.69.

Lemma 4. Let X and Y be two compact metric spaces and f : X → 2^{Y} a map such that f(x) is closed for each x ∈ X. Then the following statements are equivalent:

(i) f is upper semicontinuous.

(ii) For any two sequences (x_{m})_{m∈N}, (y_{m})_{m∈N}, the relations x_{m} → x, y_{m} ∈ f(x_{m}), y_{m} → y imply y ∈ f(x).

Theorem 5. Let {A_{1}, A_{2}, …, A_{n+1}} be a family of compact convex sets in general position in R^{n}. Then

(i) for each proper subset I of {1, 2, …, n + 1}, there exists exactly one hyperplane H such that

(10) H separates strictly the sets ∪\{A_{i} : i ∈ I\} and ∪ \{A_{j} : j ∈ \overline{I}\},

and

d(A_{1}, H) = d(A_{2}, H) = ⋯ = d(A_{n+1}, H). (11)

(ii) There exist exactly 2^{n} − 1 hyperplanes satisfying (11).

Proof. The assertion (ii) follows immediately from (i).

Let A = A_{1} × A_{2} × ⋯ × A_{n+1}. The elements of A are denoted by \overline{x}, \overline{y}, … Let I be a nonempty set of indices, arbitrarily fixed. By Lemma 3, for each \overline{x} = (x_{1}, x_{2}, …, x_{n+1}) ∈ A (x_{i} ∈ A_{i}, 1 ≤ i ≤ n + 1), there exists a unique hyperplane, denoted by H(\overline{x}), such that

d(x_{1}, H(\overline{x})) = d(x_{2}, H(\overline{x})) = ⋯ = d(x_{n+1}, H(\overline{x})) (12) and the set \{x_{i} : i ∈ I\} is situated in the open halfspace H^{>}(\overline{x}), while the set \{x_{j} : j ∈ \overline{I}\} is situated in the opposite halfspace H^{<}(\overline{x}). The equation of H(\overline{x}) is < x, b >= λ where b = (b_{1}, b_{2}, …, b_{n}) ∈ R^{n} \ {0} and λ ∈ R are given by the formulas (9).

We define the map f : A → 2^{A} by f(\overline{x}) = (P_{1}(\overline{x}), P_{2}(\overline{x}), …, P_{n+1}(\overline{x})), \overline{x} ∈ A and P_{i}(\overline{x}) defined by

(13)  \{ \begin{matrix}(a) & P_{i}(\overline{x}) = \{x ∈ A_{i} :< x, b >= min\{< y, b >: y ∈ A_{i}\}\}, & i ∈ I \\ (b) & P_{i}(\overline{x}) = \{x ∈ A_{i} :< x, b >= max\{< y, b >: y ∈ A_{i}\}\}, & i ∈ \overline{I} \end{matrix}

Since the sets A_{i} are compact, the sets P_{i}(\overline{x}) are nonempty. If y_{i} ∈ P_{i}(\overline{x}), 1 ≤ i ≤ n + 1, then P_{i}(\overline{x}) coincides with the intersection of the set A_{i} with the hyperplane parallel to H(\overline{x}) which contains the point y_{i}. Thus each P_{i}(\overline{x}) is a compact convex set, and f(\overline{x}) is a nonempty compact convex set for each \overline{x} ∈ A.

Using Lemma 4, we prove that f is upper semicontinuous. Let (\overline{x}^{m})_{m∈N}, (\overline{y}^{m})_{m∈N} be two sequences in A and \overline{x}, \overline{y} ∈ A such that \overline{x}^{m} → \overline{x}, \overline{y}^{m} → \overline{y}, \overline{y}^{m} ∈ f(\overline{x}^{m}), m ∈ N. If the hyperplanes H(\overline{x}^{m}), m ∈ N, have the equations < x, b^{m} > −λ^{m} = 0 with b^{m} = (b_{1}^{m}, b_{2}^{m}, …, b_{n}^{m}) and λ^{m} given by the formulas (9) then from \overline{x}^{m} → \overline{x}, it follows that b^{m} → b. Let i ∈ I arbitrarily fixed. Since \overline{y}^{m} ∈ f(\overline{x}^{m}), we have < y_{i}^{m}, b^{m} >≤< z_{i}, b^{m} > whenever z_{i} ∈ A_{i}. Letting m → ∞, we obtain < y_{i}, b >≤< z_{i}, b >; that is y_{i} ∈ P_{i}(\overline{x}). Using an appropriate argument, we obtain y_{i} ∈ P_{i}(\overline{x}) for each i ∈ \overline{I}, and \overline{y} ∈ f(\overline{x}). According to Lemma 4, it follows that f is upper semicontinuous.

By the Fan-Glicksberg-Kakutani fixed point theorem (see [2] and [3]), there is a point \overline{z} = (z_{1}, z_{2}, …, z_{n+1}) ∈ A such that \overline{z} ∈ f(\overline{z}). Let < x, b^{0} > −λ^{0} = 0 be the equation of the hyperplane H(\overline{z}), with b^{0} = (b_{1}^{0}, b_{2}^{0}, …, b_{n}^{0}) and λ^{0} given by the formulas (9). For each i ∈ I, z_{i} ∈ H^{>}(\overline{z}) and by the definition of f, z_{i} ∈ P_{i}(\overline{z}). Thus, we infer from (13a) that A_{i} ⊂ H^{>}(\overline{z}) for all i ∈ I.

Then, for each i ∈ I, we have

d(A_{i}, H(\overline{z})) = min \{\frac{< x, b^{0} > −λ^{0}}{∥b^{0}∥} : x ∈ A_{i}\} =

= \frac{< z_{i}, b^{0} > −λ^{0}}{∥b^{0}∥} = d(z_{i}, H(\overline{z})).

In a similar manner, we obtain that A_{j} ⊂ H^{<}(\overline{z}) and d(A_{j}, H(\overline{z})) = d(z_{j}, H(\overline{z})) for all j ∈ \overline{I}.

Therefore, H(\overline{z}) separates strictly the sets ∪\{A_{i} : i ∈ I\} and ∪\{A_{j} : j ∈ \overline{I}\} and taking into account (12), we obtain that

d(A_{1}, H(\overline{z})) = d(z_{1}, H(\overline{z})) = d(z_{i}, H(\overline{z})) = d(A_{i}, H(\overline{z}))

for each i, 2 ≤ i ≤ n + 1.

In the second part of the proof, we verify the uniqueness of the hyperplane H which satisfies (10) and (11) for an arbitrary fixed set of indices I. Note that the existance of a such hyperplane H is equivalent to the existance of two hyperplanes H_{1} and H_{2} parallel to H such that

(14) \{ \begin{matrix}H_{1} is a common supporting hyperplane to all sets A_{i}, i ∈ I, \\ H_{2} is a common supporting hyperplane to all sets A_{j}, j ∈ \overline{I}, \\ the open strip determinated by H_{1} and H_{2} is disjoint from ⋃_{i=1}^{n+1} A_{i}. \end{matrix}

By way of contradiction, suppose that there exist two hyperplanes H′ and H′′ which satisfy (10) and (11). Then there exist two pairs of parallel hyperplanes (H′_{1}, H′_{2}) and (H′′_{1}, H′′_{2}), each satisfying (14).

Obviously the sets A_{i}, i ∈ I, are contained in S_{1} = H_{1}^{′≥} ∩ H_{1}^{′′≥}. The intersection points of the sets A_{i}, i ∈ I, with H1^{′} are all situated on a face of the dihedral angle S_{1} while the intersection points of these sets with H1^{′′} are all situated on the other face of S_{1}.

Let L_{1} = H1^{′} ∩ H1^{′′} and L_{2} = H2^{′} ∩ H2^{′′}. Then L_{1} and L_{2} are two parallel (n − 2)-flats which determine together a hyperplane H_{0}. Since H_{0} separates the faces of the dihedral angle S_{1}, the convexity of A_{i} implies that H_{0} intersects all sets A_{i}, i ∈ I. Using a similar argument we obtain that H_{0} intersects all sets A_{j}, ∈ \overline{I}. Therefore H_{0} intersects each member of the family {A_{1}, A_{2}, …, A_{n+1}} which is in general position; a contradiction.

We extend the previous theorem to a family of convexly connected sets using the following result.

Lemma 6. (see [7], Th.1). Let A = {A_{i} : i ∈ I} be a family of compact convexly connected sets in R^{n}. If A is in general position then {conv A_{i} : i ∈ I} is a family of compact sets also in general position.

Corollary 7. The assertion of Theorem 5 holds if {A_{1}, A_{2}, …, A_{n+1}} is a family of compact convexly connected sets in general position in R^{n}.

Proof. By the previous lemma, Theorem 5 is applicable to the family {conv A_{1}, conv A_{2}, …, conv A_{n+1}}.

Let I be a proper subset of {1, 2, …, n+1} and let H be the unique hyperplane which satisfies the conditions

(10′)  H separates strictly the sets
∪\{conv A_{i} : i ∈ I\} and ∪\{conv A_{j} : j ∈ \overline{I}\}

and

(11′)  d(conv A_{1}, H) = d(conv A_{2}, H) = ⋯ = d(conv A_{n+1}, H).

Since two sets can be strictly separated if and only if their convex hulls can be strictly separated (see [10] p.102), the conditions (10′) and (10) are equivalent.

The inclusion A_{i} ⊂ conv A_{i} implies d(A_{i}, H) ≥ d(conv A_{i}, H), 1 ≤ i ≤ n + 1. Suppose that there exists an index i ∈ {1, 2, …, n + 1} such that

(15)  d(A_{i}, H) > d(conv A_{i}, H).

Let x ∈ conv A_{i} such that d(x, H) = d(conv A_{i}, H). By (15), the hyperplane H_{0}, parallel to H and passing through x, does not intersect the set A_{i}. Let S be the open halfspace bounded by H_{0} which does not contain H. Since A_{i} is convexly connected it is contained in S. Now, the convexity of S implies conv A_{i} ⊂ S. We obtain in this way the contradiction:

x ∈ conv A_{i} ∩ H_{0} ⊂ S ∩ H_{0} = ∅.

Therefore d(A_{i}, H) = d(conv A_{i}, H), 1 ≤ i ≤ n + 1, and the conditions (11) and (11′) are equivalent.

From (10) ⟺ (10′) and (11) ⟺ (11′) it follows that H is the unique hyperplane which satisfies (10) and (11).

Acknowledgement. The author is grateful to the referee for his careful modifications in the first version of this paper.

References

[1] T. Bisztriczky, On separated families of convex bodies, Arch. Math. 54 (1990), 193– 199.

[2] K. Fan, Fixed-point and minimax theorems in locally convex topological linear spaces, Proc. Nat. Acad. Sci. U.S.A. 38 (1952), 121–126.

[3] I. L. Glicksberg, A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points, Proc. Amer. Math. Soc. 3 (1952), 170-174.

[4] J. E. Goodman and R. Pollack, Hadwiger’s transversal theorem in higher dimensions, J. Amer. Math. Soc. 1 (1988), 301-309.

[5] O. Hanner and H. Radström, A generalization of a theorem of Fenchel, Proc. Amer. Math. Soc. 2 (1951), 589-593.

[6] V.Klee, Maximal separation theorems for convex sets, Trans. Amer. Math. Soc. 134 (1968), 133-147.

[7] H. Kramer, Supporting spheres for families of sets in product spaces, Revue d’Analyse Num. et de la Theorie de l’Appr. 2 (1973), 449-53.

[8] H. Kramer and A. B. Nemeth, Supporting spheres for families of independent convex sets, Arch. Math. 24 (1973), 91-96.

[9] H. Kramer and A. B. Nemeth, Equally spaced points for families of compact sets in Euclidean spaces, Arch. Math. 25 (1974), 198-202.

[10] T. Precupanu, Linear Topological Spaces and Fundamentals of Convex Analysis, Edit. Acad. Române, Bucureşti (1992) (in Romanian).

74 Mircea Balaj: (n+1)–Families of Sets in General Position

[11] S. Rădulescu and M. Rădulescu, Theorems and Problems in Mathematical Analysis, Edit. Did. şi Ped., Bucureşti (1982) (in Romanian).

[12] I. A. Rus, Principles and Application of the Fixed Point Theorem, Edit. Dacia, Cluj-Napoca (1979) (in Romanian).

[13] F. A. Valentine, Konvexe Mengen, Mannheim (1968). Received: May 22, 1995, revised version September 26, 1995