Placing of points into the 5-dimensional unit cube
- PDF / 158,284 Bytes
- 16 Pages / 595 x 842 pts (A4) Page_size
- 53 Downloads / 207 Views
PLACING OF POINTS INTO THE 5-DIMENSIONAL UNIT CUBE ´lint1 and Vojtech Ba ´lint jr.2 Vojtech Ba 1
Katedra kvantitat´ıvnych met´ od a hospod´ arskej informatiky ˇ ˇ Fakulta prev´ adzky a ekonomiky dopravy a spojov, Zilinsk´ a univerzita v Ziline ˇ Univerzitn´ a 1, 010 26 Zilina, Slovak Republic E-mail: [email protected] 2
Katedra kvantitat´ıvnych met´ od a hospod´ arskej informatiky ˇ ˇ Fakulta prev´ adzky a ekonomiky dopravy a spojov, Zilinsk´ a univerzita v Ziline ˇ Univerzitn´ a 1, 010 26 Zilina, Slovak Republic E-mail: [email protected] (Received April 23, 2009; Accepted November 13, 2011) [Communicated by Imre B´ ar´ any]
Abstract We give a very short survey of the results on placing of points into the unit n-dimensional cube with mutual distances at least one. The main result is that into the 5-dimensional unit cube there can be placed no more than 40 points.
1. Introduction The following problem was stated in [13] and later repeated in [14], [8], [15], [16], [1]. “Let f (n) denote the maximum number of points that can be arranged in the n-dimensional unit cube (n-cube) so that all mutual distances are at least 1. Obviously, f (n) = 2n for n ≤ 3. Determine the exact values of f (n) at least for small n.” Obviously, the problem could be formulated in terms of packing equal balls in the cube. For dimensions 3 and 4 there are known exact answers. Theorem 1. (See [17], [4].) The set of 8 vertices of the 3-cube is the only configuration which realizes f (3) = 8. Mathematics subject classification number : 52C17. Key words and phrases: unit cube, packing, distance at least 1. 1
Supported by the Discrete and Convex Geometry project MTKD-CT-2005-01433
0031-5303/2012/$20.00 c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
2
´ ´ V. BALINT and V. BALINT JR.
Theorem 2. (See [3].) f (4) = 17 and the only configuration which realizes f (4) is the 16 vertices and the centre of the 4-cube. Let M ⊂ E n be some closed convex set with diameter at least 1. It is natural to expect that if some point-set contains the maximal number of points from M with mutual distances at least 1, then this point-set contains also points, which realize the diameter of M . It is surely true for the 3-cube and also for the 4-cube, recall Theorems 1 and 2. Nevertheless, already in [3] there was constructed such an 8-gon that no two of its diagonal points can belong to an extremal arrangement. We show another, a bit simpler, example. In Figure 1.1 there is a hexagon ABF CDE with diameter |EF | = 3/2 constructed from the square ABCD with side length 1. If we choose the point E (or symmetrically F ), at most two other points can be added. But the four points A, B, C, D have all mutual distances at least 1. Therefore any of diametral points E, F cannot belong to an extremal arrangement.
D
E
C
F
1/4 1/2 A
1
B
Figure 1.1. Example of a two-dimensional object such that an extremal arrangement of points in this object cannot contain points realizing the diameter The fact that the extremal arrangement
Data Loading...
