Kirchberger-type theorems for separation by convex domains
- PDF / 189,216 Bytes
- 12 Pages / 595 x 842 pts (A4) Page_size
- 43 Downloads / 145 Views
KIRCHBERGER-TYPE THEOREMS FOR SEPARATION BY CONVEX DOMAINS ´ngi1 and Ma ´rton Naszo ´ di2 Zsolt La 1
2
Dept. of Geometry, Budapest University of Technology Budapest, Egry J´ ozsef u. 1., Hungary, 1111 E-mail: [email protected]
Dept. of Math. and Stats., 632 Central Academic Building University of Alberta, Edmonton, AB, Canada, T6G 2G1 E-mail: [email protected] (Received March 24, 2008; Accepted September 25, 2008)
Abstract We say that a convex set K in Rd strictly separates the set A from the set B if A ⊂ int(K) and B ∩ cl K = ∅. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in Rd with the property that for every T ⊂ A ∪ B of cardinality at most d + 2, there is a half space strictly separating T ∩ A and T ∩ B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in Rd is d + 2. In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.
1. Introduction and preliminaries A fundamental theorem in the study of separation properties of sets in Euclidean d-space Rd is the Theorem of Kirchberger [7]. It states that, for any two Mathematics subject classification numbers: 52A35, 52A20, 52A99. Key words and phrases: separation, Theorem of Kirchberger, convex set. 1
Partially supported by the Alberta Ingenuity Fund.
2
Partially supported by a postdoctoral fellowship of the Pacific Institute for the Mathematical Sciences.
0031-5303/2008/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
186
´ ´ Z. LANGI and M. NASZODI
finite sets A and B in Rd , A and B are strictly separable by a half space, if for any T ⊂ A ∪ B of cardinality at most d + 2, T ∩ A and T ∩ B are strictly separable by a half space. Let Bd [x, r] denote the closed Euclidean ball of radius r with x as centre d in R . Houle [6] proved the following. If A and B are finite sets in Rd , and, for any T ⊂ A ∪ B of cardinality at most d + 2, there is a ball Bd [xT , rT ] such that T ∩ A ⊂ int Bd [xT , rT ] and T ∩ B ⊂ Rd \ Bd [xT , rT ], then there is a ball Bd [x, r] such that A ⊂ int Bd [x, r] and B ⊂ Rd \ Bd [x, r]. In [1] the following strengthening of this result is proved: If for every T , we have that rT ≤ 1 in the preceding statement, then there is a ball Bd [x, r] strictly separating A from B with r ≤ 1. For simplicity, we call a (possibly unbounded) closed, convex set with nonempty interior a convex domain. A compact convex domain is a convex
Data Loading...
