EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 2, 2023, 893-898 ISSN 1307-5543 – ejpam.com Published by New York Business Global On the Partition of Space by Hyperplanes Armen Bagdasaryan College of Engineering and Technology, American University of the Middle East, Egaila 54200, Kuwait Abstract. We consider the problem of partitioning of space by hyperplanes that arises in many ap- plication areas, where the number of regions the space is divided into is required to be determined, such as speech/pattern recognition, various classification problems, data analysis. We obtain some relations for the number of divisions and establish a recurrence relation for the maximum number of regions in d-dimensional Euclidean space cut by n hyperplanes. We also re-derive an explicit formula for the number of regions into which the space can be partitioned by n hyperplanes. 2020 Mathematics Subject Classifications: 52C35, 51M20, 05A19, 14N20, 32S22 Key Words and Phrases: Hyperplanes in Rd, partition of Rd, hyperplane arrangement, number of regions, k-edge of a family of hyperplanes, binomial coefficients 1. Introduction and preliminaries The problem of partitioning of d-space (or, points in d-space) by a set of hyperplanes (a single hyperplane) has been the subject of multiple works. It is an interesting problem in its own right (see [1, 4, 8, 11]), but the problem has been considered not only for its general mathematical interest. The question of how many such partitions are possible arises in various applications, for example, in the theory of pattern classification and machine learning [3, 5, 10] which employs partitions using some number k of parallel hyperplanes; in cluster analysis [6] dealing with the methods of partitioning of a set of objects on the basis of their characteristics or properties into clusters or groups so that the objects of a cluster are closely related according to certain criteria; data analysis and classification in which space partitioning by hyperplanes may be used together with linear regression techniques based on least absolute value estimates approach and its generalizations; in the theory of hybrid systems and control [9]. The problem has been generalized and analyzed in different ways, e.g. [7] considers the division of d-space by topological hyperplanes, subspaces of Rd or homeomorphs of it, that is topological equivalent to an ordinary straight hyperplane, and in [2] partitioning by the polynomial separating surfaces has been studied. In this note we deal with the partitions of Rd that may naturally arise in the problems of clustering or classification considered in discrete form. DOI: https://doi.org/10.29020/nybg.ejpam.v16i2.4713 Email address: armen.bagdasaryan@aum.edu.kw (A. Bagdasaryan) https://www.ejpam.com 893 © 2023 EJPAM All rights reserved. A. Bagdasaryan / Eur. J. Pure Appl. Math, 16 (2) (2023), 893-898 894 Let us first introduce the notations. We use the term hyperplane in Rd to mean an affine subspace of codimension one in Rd, i.e. a (d− 1)-dimensional straight plane in Rd which need not necessarily pass through the origin. Let H be a family of n distinct hyperplanes {hi}i=1,...,n in the d-dimensional space Rd, where d and n are arbitrary positive integers. We denote by GH(d, n) = Gh1,h2,...,hn(d, n) the number of regions into which the space Rd is partitioned by the hyperplanes h1, h2, . . . , hn, that is the number of connected components of the set Rd \H = Rd \ (h1 ∪ h2 ∪ . . . ∪ hn). We also set G(d, n) = max H GH(d, n). Any nonvoid intersection of hyperplanes of the family H is referred to as an edge of the family. The edge of dimension k, which is a k-dimensional plane, is called a k-edge and denoted by Ek, k = 0, 1, . . . ,m. We let Ek [t] denote a k-edge made of intersections of any j = 1, . . . , t hyperplanes, Ek [1,t] a k-edge made of intersections of all of h1, h2, . . . , ht hyperplanes, and Ek [1,t;n] a k-edge made of intersections of each hi with hn, i ̸= n. In these terms the space Rd can be considered as a d-dimensional edge of the family H. Each separating surface in Rd, represented as a hyperplane, is given by a linear equation hi = {x ∈ Rd | aix = bi}, or equivalently hi(x) ≡ d∑ j=1 aijxj − bi = 0, i = 1, . . . , n. (1) Then the classification problem in discrete form can typically be formulated as follows. Given the probabilities pτ of appearance of each of N objects x̃1 = (x11, . . . , x1d), . . ., x̃τ = (xτ1, . . . , xτd), . . ., x̃N = (xN1, . . . , xNd) and information about belonging of each object to a certain class, one needs to distinguish s classes C1, . . . , Ck, . . . , Cs in the space of parameters Rd. The rule that determines the assignment of the object x̃ to a class can be defined as x̃ ∈  C1, hα(x) ≥ 0, α ∈ I1; hβ(x) < 0, β ∈ J1 C2, hα(x) ≥ 0, α ∈ I2; hβ(x) < 0, β ∈ J2 ... ... ... ... ... Cs, hα(x) ≥ 0, α ∈ Is; hβ(x) < 0, β ∈ Js (2) where Ik, Jk, k = 1, . . . , s, are the predefined index sets. Hence, the points x̃′ and x̃′′ lie in different regions if and only if there exists an index i for which hi (x̃ ′) and hi (x̃ ′′) have different signs. For this purpose the sign vector-function, the partition signature, f : Rd → {−,+}n defined as fi(x) ∈ { −, if aix ≤ bi +, if aix > bi , i = 1, . . . , n can be employed for the analysis of the classification schemes with different rules. Therefore, the problem of classification has two different formulations. Direct problem: find the minimum number of hyperplanes (1) that divide Rd into s regions according to the rule (2); Inverse problem: determine the maximum number of regions into which Rd can be divided by means of n hyperplanes (1) according to the rule (2). A. Bagdasaryan / Eur. J. Pure Appl. Math, 16 (2) (2023), 893-898 895 2. Main Results The main results of this paper are contained in the propositions presented below. Theorem 1. Suppose that H(x) = {h1(x), h2(x), . . . , hn(x)} is a collection of hyperplanes in Rd. Let H′ ⊂ H be the partition of Rd by n − 1 hyperplanes and H′′ ⊂ H′ be the partition of Rd−1 by ℓ hyperplanes, ℓ < n. Then we have GH(d, n) = GH′(d, n− 1) +GH′′(d− 1, ℓ) ≤ G(d, n− 1) +G(d− 1, n− 1). (3) Proof. Without loss of generality, we can assume that the coordinate system in Rd is chosen in such a way that hn(x) coincides with Rd−1 ⊂ Rd and is defined by the equation xd = 0. The hyperplanes h1(x), . . . , hn−1(x) divide Rd into GH′(d, n − 1) ≤ GH(d, n − 1) regions. The hyperplane hn(x) divides some of these regions into two other regions. The boundaries of these latter regions are (d − 1)-dimensional regions that lie in hn(x); or, if hn(x) is parallel to the all hi(x), i ̸= n, then the whole hn(x) is the boundary hyperplane. Hence, we have that the number of regions contributed by the hyperplane hn(x) coincides with the number of regions formed in hn(x) by some number ℓ of k-edges Ek [1,n−1;n],j , j = 1, . . . , ℓ, k ≤ d − 1, of intersection of hn(x) with each hi(x), i = 1, . . . , n − 1, or, equivalently, generated by the “lines” of intersection of hn(x) with each hi(x); moreover, hn(x) contributes only one region if it is parallel to the all hi(x), i = 1, . . . , n − 1. The number of such lines is equal to ℓ ≤ n − 1. Therefore, the number of new regions is GH′′(d − 1, ℓ) ≤ G(d − 1, n − 1), from which the inequality (3) immediately follows. The proof is completed. Corollary 1. Suppose that for the partition H(x) it holds that GH(d, n) = G(d, n). Then we have G(d, n) ≤ G(d, n− 1) +G(d− 1, n− 1). (4) Remark 1. Since GH′′(d − 1, 0) = 1, the relation (3) holds also in “parallel” case, that is, in the case when hn(x) is parallel to the all hi(x), i ̸= n. In the next theorem we obtain the recurrence formula for the number of regions. Theorem 2. Let A = [aij ] , i = 1, . . . , n, j = 1, . . . , d be the matrix of coefficients of the equation (1). Further, suppose that the partition H(x) = {hi(x), i = 1, . . . , n} of Rd is such that every set of k rows, k ≤ d, of A has the rank k, i.e. rankk≤d [aij ] = k. Then we have GH(d, n) = G(d, n− 1) +G(d− 1, n− 1), (5) that is, GH(d, n) takes on the maximal value. Proof. We prove the theorem by induction over n. It is straightforward to check that for n = 1 the statement of theorem is true, since G(d, 1) = 2 and G(d, 0) = G(d−1, 0) = 1. Suppose that the theorem holds true for the partition by (n− 1) hyperplanes. Now let h1(x), h2(x), . . . , hn(x), where hn(x) = Rd−1, be the hyperplanes satisfying the theorem’s A. Bagdasaryan / Eur. J. Pure Appl. Math, 16 (2) (2023), 893-898 896 condition. Then it is obvious to see that the partition H′(x) = {h1(x), h2(x), . . . , hn−1(x)} satisfies the condition of the theorem as well, so that by induction we have GH′(d, n−1) = G(d, n − 1). The equations of k-edges, k ≤ d − 1, h′i(x) as the “lines” of intersection of hi(x) with hn(x), i ̸= n, has the following form h′i(x) ≡ d−1∑ j=1 aijxj − bi = 0, i = 1, . . . , n− 1, (6) regarding h′i(x) as the hyperplanes in Rd−1. Now it is sufficient to show that the partition H′′(x) = {h′1(x), h′2(x), . . . , h′n−1(x)} of hn(x) = Rd−1 satisfies the condition of the theorem. Indeed, assume that the set of k ≤ d − 1 rows (aνi,1, aνi,2, . . . , aνi,d−1), i = 1, 2, . . . , k, of coefficients {aij} in (6) has the rank r < k. Then we get that the set of rows (aνi,1, aνi,2, . . . , aνi,d−1, aνi,d), i = 1, 2, . . . , k, together with the row (0, . . . , 0, 1) of coefficients of the equation hn(x) = 0 has the rank r+ 1 ≤ k, less than the number of rows k+ 1, which contradicts the theorem’s condition. Therefore, by the induction we again have that GH′′(d− 1, n− 1) = G(d− 1, n− 1), from which the statement of the theorem follows. The proof is completed. Remark 2. The existence of the partition H that satisfies the condition of Theorem 2 is provided by and can be deduced from the fact that Rd contains infinitely many hyperplanes. The following result is well-known [1, 4, 12]. Here, we give an alternative proof of this result by re-deriving the statement using the formula (5) of Theorem 2. Theorem 3. It holds that G(d, n) = d∑ k=0 ( n k ) , (7) where ( n k ) = n! k!(n−k)! , k ≤ n and ( n k ) = 0 if k > n. Proof. Consider the recurrence relation G(d, n) = G(d, n− 1) +G(d− 1, n− 1) (8) for the maximum number of regions that can be obtained by partitioning of Rd by n hyperplanes (see eq. (5)), together with the initial conditions G(d, 0) = 1, d = 1, 2, . . . . (9) The number G(d, n) is uniquely defined by (8), (9). Indeed, the values of G(d, 0) are known for all d. Hence, if the value of G(d, n) is known for all pairs (d, n) for which n = k − 1, then G(d, k) can be found from (8) for any d. Now it is sufficient to show that (7) satisfies (8) and (9). Substituting (7) into (8), we get d∑ k=0 ( n k ) = d∑ k=0 ( n− 1 k ) + d∑ k=1 ( n− 1 k − 1 ) . (10) REFERENCES 897 The equality (10) is in fact the identity which can be established using the combinatorial formula ( n k ) = ( n− 1 k ) + ( n− 1 k − 1 ) . It is easy to see that (7) satisfies the condition (9), which completes the proof. 3. Conclusions and Further Work In this paper we have investigated the problem of space partitioning by hyperplanes. We obtained some relations regarding the number of divisions and derived the recurrence formula for the maximum number of regions in d-dimensional Euclidean space cut by n hyperplanes in arbitrary position. An explicit formula for the number of regions into which the space can be partitioned by n hyperplanes can also be found. Using the re- currence formula, we gave an alternative derivation of the well known explicit formula for the number of regions that n hyperplanes in general position divide the d-dimensional space. In our subsequent works we plan to continue studying the combinatorics of hyper- plane configurations in Rd. Further work may address the investigation of the number of k-edges of hyperplane configurations, the study of partitioning problem of Rd by hyper- planes with the use of Möbius function defined on finite posets connected with the rank of homology group Hd (Cn \H), the study of separating subgroups of the homology group Hd (Cn \H), and finding the formulas for Möbius function of posets of edges of hyperplane configurations. These results may find applications in toric geometry, singularity theory and multidimensional residues, and the theory of hypergeometric functions. Yet another direction of future research may be related to the application of the obtained results in data analysis and classification, and experimental data processing using linear regression models, and in the problems of identifiability of linear dynamical systems in state space. Acknowledgements The author wishes to thank the anonymous referees for useful comments that improved the presentation of this paper. References [1] G L Alexanderson and G E Wetzel. Divisions of space by parallels. Trans. Amer. Math. Soc., 291:363–377, 1985. [2] M Anthony. Classification by polynomial surfaces. Discrete Appl. Math., 61:91–103, 1995. [3] M Anthony and P L Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. [4] R C Buck. Partition of space. Amer. Math. Monthly, 50:541–544, 1943. REFERENCES 898 [5] R O Duda, P E Hart, and D Stork. Pattern Classification. Wiley, 2000. [6] B Everitt, S Landau, M Leese, and D Stahl. Cluster Analysis. Wiley, 2011. [7] D Forge and T Zaslavsky. On the division of space by topological hyperplanes. Eu- ropean J. Combin., 30:1835–1845, 2009. [8] Ch Ho and S Zimmerman. On the number of regions in an m-dimensional space cut by n hyperplanes. Gaz. Austr. Math. Soc., 8:260–264, 2006. [9] T Geyer, F Torrisi and M Morari. Optimal complexity reduction of piecewise affine models based on hyperplane arrangements. In Proceedings of the 2004 American Control Conference., pages 1190–1195, Boston, MA, 2004. IEEE. [10] V N Vapnik. Statistical Learning Theory. Wiley, 1998. [11] R.O. Winder. Partitions of N -space by hyperplanes. SIAM J. Appl. Math., 14:811– 818, 1966. [12] S Zimmerman. Slicing space. College Math. J., 32:126–128, 2001.