On the orthogonal Grünbaum partition problem in dimension three
April 01, 2024
Abstract
Grünbaum’s equipartition problem asked if for any measure on \(\mathbb{R}^d\) there are always \(d\) hyperplanes which divide \(\mathbb{R}^d\) into \(2^d\) \(\mu\)-equal parts. This problem is known to have a positive answer for \(d\le 3\) and a negative one for \(d\ge 5\). A variant of this question is to require the hyperplanes to be mutually orthogonal. This variant is known to have a positive answer for \(d\le 2\) and there is reason to expect it to have a negative answer for \(d\ge 3\). In this note we exhibit measures that prove this. Additionally, we describe an algorithm that checks if a set of \(8n\) in \(\mathbb{R}^3\) can be split evenly by \(3\) mutually orthogonal planes. To our surprise, it seems the probability that a random set of \(8\) points chosen uniformly and independently in the unit cube does not admit such a partition is less than \(0.001\).
1 Introduction↩︎
Let \(\mu\) be a finite Borel measure on \(\mathbb{R}^d\), we say that \(\mu\) is a mass if it vanishes on every affine hyperplane. A collection of hyperplanes \(H_1,H_2,\dots,H_d\subset\mathbb{R}^d\) define an equipartition of a mass \(\mu\) if these hyperplanes divide \(\mathbb{R}^d\) into \(2^d\) parts of equal \(\mu\)-measure. The problem of determining the values of \(d\) for which any mass has an equipartition was proposed by Grünbaum in 1960 [1] and is a special case of the Grünbaum-Hadwiger-Ramos mass partition problem [2], [3]. Grünbaum’s problem has an affirmative answer for \(d\le 3\) [4], [5], a negative one for \(d\ge 5\) [6] and is unknown for \(d=4\).
We are interested in a variant of Grünbaum’s problem where an additional condition is imposed, namely, that the hyperplanes defining the equipartition be mutually orthogonal. In this way, we say that the hyperplanes \(H_1,H_2,\dots,H_k\subset\mathbb{R}^d\) define an orthogonal equipartition of \(\mu\) if these hyperplanes are mutually orthogonal and divide \(\mathbb{R}^d\) into \(2^k\) parts of equal \(\mu\)-measure.
Question 1. Is it true that every mass \(\mu\) on \(\mathbb{R}^d\) has an orthogonal equipartition defined by \(d\) hyperplanes?
The purpose of this paper is to answer this question negatively for \(d\ge 3\). It is well known that the answer is affirmative for \(d\le 2\) and thanks to Avis’ work [6] we know it to be negative for \(d\ge 5\).
Theorem 1. For every \(d\ge 3\) there exists a finite Borel measure on \(\mathbb{R}^d\) that has no orthogonal equipartition defined by \(d\) planes.
From a topological point of view, this result is expected. This is because the space of triples consisting of mutually orthogonal planes in \(\mathbb{R}^3\) has dimension \(6\) but, in order for such a triple to define an orthogonal equipartition of \(\mu\), \(7\) independent constraints must be satisfied. Since the number of constraints is larger that the dimension of the space, no triple of mutually orthogonal planes should satisfy all the constraints for some generic measure \(\mu\).
Some of the main ideas used to prove Theorem 1 are similar to the ones used by Avis. Both in his and our approach, the measures constructed are supported on the moment curve. In Section 2 we present the tools and definitions used to prove Theorem 1.
We also study an equivalent problem where the measures are replaced by point-sets. Given a set of \(8n\) points in \(\mathbb{R}^3\), an orthogonal equipartition of \(X\) is a partition of \(X\) into \(8\) sets consisting of \(n\) points each which can be separated by using \(3\) mutually orthogonal planes. In Section 3 we describe an algorithm that is capable of finding all orthogonal equipartitions \(X\).
Theorem 2. Let \(X\) be a set of \(8n\) points in \(\mathbb{R}^3\), then the set of all orthogonal equipartitions of \(X\) can be found in time \(O(n^7)\).
There is a previous algorithm, described in [7], that runs in time \(O(n^{15/2}\log(n))\). We believe the time complexity in our algorithm can be further reduced to \(O(n^5\log(n))\). For the \(2\)-dimensional version of this problems there is an algorithm that finds all equipartitions in time \(O(n\log(n))\) [8].
A surprising thing that we found is almost all random sets of points we explored have orthogonal equipartitions defined by three planes. We considered sets of either \(8\) or \(16\) random points chosen uniformly and independently in a cube. Of these only a fraction of around \(0.0009\) sets of \(8\) points and of \(0.0007\) sets of \(16\) points failed to have such an equipartition. This came as a surprise to us in view of the topological intuition described above.
2 Orthogonal hyperplanes and the moment curve↩︎
The standard moment curve in \(\mathbb{R}^d\) is defined parametrically by the mapping \[\gamma(t)=\left(t,t^2,\dots,t^d\right)\] for \(t\in\mathbb{R}\).
In order to prove Theorem 1 we require a few lemmas. The first one is probably well-known but we include a short proof. In simple words it states that not all elements in an orthonormal basis can be too far from any given direction.
Lemma 2. Let \(\{u_1,\dots,u_d\}\) be an orthonormal basis of \(\mathbb{R}^d\) and let \(v\in\mathbb{R}^d\) be a unit vector. Then there is an \(i\in\{1,\dots,d\}\) such that \(\lvert \left\langle u_i,v \right\rangle \rvert\ge 1/\sqrt{d}\).
Proof. Consider the hypercube with faces orthogonal to the \(u_i\). Let \(w = (u_1+\dots+u_d)/\sqrt d\), then \(w\) is a unit vector which defines a line through two opposite corners of this hypercube. There is an \(i\in\{1,\dots,d\}\) such that the line generated by \(v\) crosses the two opposite faces \(F_1\) and \(F_2\) orthogonal to \(u_i\). Note that the line defined by \(w\) passes through corners of \(F_1\) and \(F_2\). It follows that \(\lvert \left\langle u_i,v \right\rangle \rvert\ge \lvert \left\langle u_i,w \right\rangle \rvert=1/\sqrt{d}\). ◻
For large \(M\), the part of the moment curve with \(t\ge M\) behaves like a vertical line since its last coordinate dominates the rest. This is exploited in the final lemma.
Lemma 3. For every \(d\ge 2\) there is a number \(M_d>0\) such that the following holds: If \(H_1,H_2,\dots, H_d\) are mutually orthogonal hyperplanes in \(\mathbb{R}^d\), then the part of the moment curve defined by \[\Gamma=\{\gamma(t):t\ge M_d\}\] intersects some \(H_i\) in at most one point.
Proof. Let \(u_i\) be the vector normal to \(H_i\) with non-negative last coordinate. If \(e_d=(0,\dots,0,1)\in \mathbb{R}^d\), then Lemma 2 implies that one of the \(u_i\), say \(u_1\), satisfies \[\left\langle u_1,e_d \right\rangle\ge \frac{1}{\sqrt d}.\]
Assume that \(H_1\) intersects \(\Gamma\) at two distinct points \(\gamma(a)\) and \(\gamma(b)\) with \(0<a,b\). Then the vector \(v = \frac{1}{b-a}(\gamma(b) - \gamma(a))\) is parallel to \(H\) and therefore \(\left\langle u_1,v \right\rangle=0\). Note that \[v = \frac{\gamma(b)-\gamma(a)}{b-a} = (1,S_1,S_2,\dots,S_{d-1}),\] where \(S_n = a^n+a^{n-1}b+\dots+ab^{n-1}+b^n\).
If \(u_1=(x_1,\dots,x_d)\) then \(x_d=\left\langle u_1,e_d \right\rangle\ge 1/\sqrt d\) and therefore \[\begin{align} 0 & = \left\langle u_1,v \right\rangle = x_1 + x_2 S_1+\dots x_d S_{d-1}\\ & > x_1 - S_1-\dots - S_{d-2} + \frac{S_{d-1}}{\sqrt{d}}, \end{align}\] so \[\label{eq:} x_1 < S_1 + \dots + S_{d-2} - \frac{S_{d-1}}{\sqrt{d}}.\tag{1}\] The right-hand side of this inequality is a polynomial on \(a\) and \(b\), and satisfies that the coefficients multiplying the terms of maximal degree are negative. Therefore, if \(M_d\) is large enough and \(M_d\le a,b\), then 1 implies \(x_1<-1\) which contradicts \(\|u_1\|=1\). ◻
For \(d=3\) it is not hard to see that we may choose \(M_3<2\). On the other hand, there does exist a triple of mutually orthogonal planes such that each of them intersects \(\{\gamma(t):t\ge 0\}\) in at least \(2\) points.
Now we are ready to prove out main theorem.
Proof of Theorem 1. Let \(M_d\) and \(\Gamma\) be as in Lemma 3 and let \(\mu\) be any finite Borel measure supported on \(\Gamma\). Assume that \(\mu\) has an orthogonal equipartition defined by the planes \(H_1,\dots, H_d\), then there must be a segment of positive length of \(\Gamma\) in each of the \(2^d\) connected components of \(\mathbb{R}^d\setminus(H_1\cup\dots\cup H_d)\). This implies that \(\Gamma\) must intersect \(H_1\cup\dots\cup H_d\) at least \(2^d-1\) times.
By Lemma 3 there is a plane, say \(H_1\), which \(\Gamma\) intersects only once. Since \(\Gamma\) is a subset of the moment curve, \(\Gamma\) intersects every \(H_i\), with \(i>1\) in at most \(d\) points. Therefore, the number of intersection points between \(\Gamma\) and \(H_1\cup\dots\cup H_d\) is at most \(1+d(d-1)\) which, for \(d\ge 4\), is less than \(2^d-1\). This proves that no collection of \(d\) mutually orthogonal hyperplanes defines an equipartition of \(\mu\) when \(d\ge 4\).
For \(d=3\) we have that \(d(d-1)+1 = 7 = 2^d-1\) so there is more to be done. Below we show that in this case there is a second plane which intersects \(\Gamma\) in at most \(2\) points.
Assume that a plane \(H\) with normal vector \(u\) intersects \(\Gamma\) at three points \(\gamma(a)\), \(\gamma(b)\) and \(\gamma(c)\) with \(0 < a, b, c\). Then the vector \(v = \frac{1}{(a-b)(a-c)(b-c)}(\gamma(b)-\gamma(a)) \times (\gamma(c)-\gamma(a))\) is orthogonal to \(H\) and therefore parallel to \(u\). Note that \[v = (1,-a-b-c,ab+ac+bc).\] Let \(y=a+b+c\) and \(z=ab+ac+bc\), then clearly \(0<y,z\).
If \(\Gamma\) intersects \(H_2\) and \(H_3\) in at least \(3\) points each, their normal vectors \(u_2\) and \(u_3\) are parallel to vectors of the form \((1,-y_2,z_2)\) and \((1,-y_3,z_3)\) with \(0<y_2,z_2,y_3,z_3\). Since \(H_2\) and \(H_3\) are orthogonal, \[0=\left\langle (1,-y_2,z_2),(1,-y_3,z_3) \right\rangle=1+y_2y_3+z_2z_3 > 1,\] which is a contradiction. Thus, either \(H_2\) or \(H_3\) intersects \(\Gamma\) in at most \(2\) points. Therefore, the number of intersection points between \(\Gamma\) and \(H_1,H_2,H_3\) is at most \(6\), which is less than \(2^3-1\), proving that no collection of \(3\) mutually orthogonal planes defines an equipartition of \(\mu\) when \(d=3\). ◻
We showed that, for \(d=2\), \(\Gamma\) intersects any pair of orthogonal lines in at most \(3\) points. For \(d=3\), \(\Gamma\) intersects any triple of mutually orthogonal planes in at most \(6\) points. It might be possible that, for arbitrary \(d\), \(\Gamma\) intersects any \(d\)-tuple of hyperplanes in at most \(d(d+1)/2\) points, however we have not attempted to verify this.
3 Discrete partition problem↩︎
In this section we study a discrete version of Question 1 where we consider point-sets instead of measures.
We say that a set of points in \(\mathbb{R}^3\) is in general position if, from \(X\), no \(3\) points are colinear, no \(4\) points are coplanar, no \(6\) points are in the union of \(2\) orthogonal planes, and no \(7\) points are in the union of \(3\) orthogonal planes. Note that this is what is expected for sets of points generated randomly, so this can be achieved by perturbing any given set of points. It is easy to see that, if \(\lvert X \rvert\ge 7\), it is enough to ask for the condition that no \(7\) points are in the union of \(3\) orthogonal planes in order to satisfy the rest.
Recall that an oriented plane \(H\subset\mathbb{R}^3\) divides \(\mathbb{R}^3\) into two open half-spaces called the positive and negative sides, we denote them by \(H^+\) and \(H^-\), respectively. Suppose we have a triple of intersecting oriented planes \(H_1,H_2,H_3\), then for any choice of signs \(s_1,s_2,s_3\in\{+,-\}\) we have a closed region defined by \[\label{eq:regions} \bigcap_{i\in\{1,2,3\}} \overline{H_i^{s_i}}.\tag{2}\] Assume that \(X\) is a set with \(8n\) points in \(\mathbb{R}^3\), and the sets \(X_1,\dots,X_8\) form a partition of \(X\). We say that this partition is an orthogonal equipartition of \(X\) if each \(X_i\) has \(n\) points and there exist three orthogonal oriented planes \(H_1,H_2,H_3\) together with bijections \(X_i\mapsto R_i\) which assigns to each \(X_i\) one of the \(8\) regions \(R_i\) defined in 2 such that \(X_i\subset R_i\). In this case we say that the planes \(H_1,H_2,H_3\) certify the equipartition.
Our algorithm is based on the following key observation that has a standard and straightforward proof.
Lemma 4. If \(X\) has an orthogonal equipartition certified by the planes \(H_1,H_2,H_3\), then there are planes \(H_1',H_2',H_3'\) that also certify this partition and whose union contains exactly \(6\) points from \(X\).
In the opposite direction, it is possible to show that one may always perturb the planes in order to obtain a triple of mutually orthogonal planes containing no points from \(X\) which certify the same equipartition.
Assume that \(\lvert H_1\cap X \rvert\ge \lvert H_2\cap X \rvert\ge \lvert H_3\cap X \rvert\), then there are only two possibilities: either \(\lvert H_1\cap X \rvert=3\), \(\lvert H_2\cap X \rvert=2\) and \(\lvert H_3\cap X \rvert=1\), or \(\lvert H_1\cap X \rvert=\lvert H_2\cap X \rvert=\lvert H_3\cap X \rvert=2\).
Let \(A_1, A_2, A_3\subset\mathbb{R}^3\) be finite sets such that \(A_1\cup A_2\cup A_3\) is in general position. If \(\lvert A_1 \rvert=3\), \(\lvert A_2 \rvert=2\) and \(\lvert A_1 \rvert=1\) then it is easy to see that there is a unique triple of orthogonal planes \(H_1\), \(H_2\) and \(H_3\) containing \(A_1\), \(A_2\) and \(A_3\), respectively. Computing these planes is also straightforward. If \(A_1=A_2=A_3=2\) then there is at most one triple of orthogonal planes \(H_1\), \(H_2\) and \(H_3\) containing \(A_1\), \(A_2\) and \(A_3\), respectively. This triple can be computed in the following way.
First, for each \(i\in\{1,2,3\}\), consider the vectors \(v_i\) which are the difference between the two points in \(A_i\). The planes \(H_1,H_2,H_3\) should be mutually orthogonal and satisfy that \(v_i\in H_i\). If \(u_i\) is a unit normal vector to \(H_i\) then this is equivalent to \(u_1,u_2,u_3\) being an orthonormal basis satisfying \(u_i \perp v_i\).
Choose \(a,b\) as two independent vectors, whose linear span does not contain any of the \(v_i\). Take a basis of \(v_i^\perp\), for example \(a_{i} = a\times v_i\) and \(b_{i} = b\times v_i\). In order for \(u_i\perp v_i\), each \(u_i\) should then be a linear combination of \(a_i\) and \(b_i\). To simplify, assume that the coefficient of \(b_i\) is \(1\) and let \[u_i = \alpha_i a_i + b_i.\] For these vectors to be orthogonal we require, for each \(i\in\{1,2,3\}\), \[\begin{align} 0=u_i\cdot u_{i+1}&=\alpha_i\alpha_{i+1} (a_i\cdot a_{i+1}) +\alpha_i (a_i\cdot b_{i+1})+\alpha_{i+1} (b_i\cdot a_{i+1}) + (b_i\cdot a_{i+1})\\ &=A_i \alpha_i\alpha_{i+1} +B_i\alpha_i+C_i\alpha_{i+1} + D_i, \end{align}\] where the indices are taken modulo \(3\) and \[\begin{align} A_i = a_i\cdot a_{i+1}, \qquad B_i = a_i\cdot b_{i+1}, \qquad C_i = b_i\cdot a_{i+1}, \qquad D_i = b_i\cdot a_{i+1}, \end{align}\] This is a system of three quadratic equations whose solutions are given by \[\label{eq:alpha} \alpha_i = \frac{r_i\pm\sqrt{q}}{2s_i},\tag{3}\] where \[\begin{align} q & = (A_1 B_3 D_2-A_1 C_2 D_3+A_2 B_1 D_3+A_2 C_3 D_1\\ &\quad\qquad\qquad -A_3 B_2 D_1+A_3 C_1 D_2-B_1 B_2 B_3-C_1 C_2 C_3)^2 \\ &\quad +4 (A_1 A_3 D_2-A_1 C_2 C_3+A_2 B_1 C_3-A_3 B_1 B_2) \\ &\quad\qquad\qquad (-A_2 D_1 D_3+B_2 B_3 D_1-B_3 C_1 D_2+C_1 C_2 D_3), \\ r_i & = A_i B_{i+2} D_{i+1}-A_i C_{i+1} D_{i+2}+A_{i+1} B_i D_{i+2}+A_{i+1} C_{i+2} D_i\\ &\quad-A_{i+2} B_{i+1} D_i+A_{i+2} C_i D_{i+1}-B_i B_{i+1} B_{i+2}-C_i C_{i+1} C_{i+2}, \\ s_i & = - A_i A_{i+2} D_{i+1} + A_i C_{i+1} C_{i+2} - A_{i+1} B_i C_{i+2} + A_{i+2} B_i B_{i+1}). \end{align}\] If \(q<0\), there is no real solution and therefore there does not exist a triple of planes \(H_1,H_2,H_3\) satisfying the desired properties. If \(s_i=0\), we may not assume that \(b_i=1\). In other words, there may be a solution where \(u_i=b_i\). These cases should also be checked. Once we have found the vectors \(u_1,u_2,u_3\) one only needs to construct the planes \(u_1^\perp,u_2^\perp,u_3^\perp\) and translate them appropriately in order to determine \(H_1,H_2,H_3\). Because of the choice of the sign in 3 , there are \(8\) possible real solutions, these correspond to triples of vectors of the form \(\pm u_1,\pm u_2,\pm u_3\) which all give raise to the same triple of planes.
For our computational goals it is important to notice that the value of \(q\) in 3 does not depend on the index, so the parameters defining the planes \(H_1,H_2,H_3\) have coefficients in \(\mathbb{Q}[\sqrt{q}]\). This means that, if \(q\ge 0\), we can determine precisely whether any given point lies on the positive or negative side of a plane.
Figure 1: Finding an orthogonal equipartition in dimension \(3\).
Now we are ready to describe Algorithm 1. It receives as input a set of \(8n\) points in general position. First it looks at all possible triples \(A_1,A_2,A_3\subset X\) with \(\lvert A_1 \rvert=3\), \(\lvert A_2 \rvert=2\) and \(\lvert A_3 \rvert=1\) and uses the function planes_321 to construct the triple of orthogonal planes \(H_1,H_2,H_3\) satisfying \(H_1\cap X=A_1\), \(H_2\cap X=A_2\) and \(H_3\cap X=A_1\). The function PARTITIONS then constructs all possible partitions of \(X\) certified by these planes by assigning the possible regions to each to the \(6\) points from \(X\) in \(H_1\cup H_2\cup H_3\). If all parts have the same size, the partition is added to the list of orthogonal equipartitions.
Afterwards it looks at thee triples \(A_1,A_2,A_3\subset X\) with \(\lvert A_1 \rvert=\lvert A_2 \rvert=\lvert A_3 \rvert=2\) and uses the function PLANES_222 to construct, whenever they exist, the triple of orthogonal planes \(H_1,H_2,H_3\) satisfying \(H_1\cap X=A_1\), \(H_2\cap X=A_2\) and \(H_3\cap X=A_1\). If the planes do exist then the algorithm proceeds as above.
We are left with the set of all possible orthogonal equipartition of \(X\).
Our algorithm runs in time \(O(n^7)\) since it takes \(O(n^6)\) time to iterate over the sets \(A_1,A_2,A_3\) and for each of these it requiers another \(O(n)\) to check if the partition is an equipartition. We believe that this can be improved to \(O(n^{9/2} \log(n))\) since, in all sets \(X\) of points we tested, whenever \(X\) had an equipartition it could be certified with planes satisfying \(\lvert H_1\cap X \rvert=3\), \(\lvert H_2\cap X \rvert=2\) and \(\lvert H_3\cap X \rvert=1\). If only these planes were needed to verify that a set \(X\) has no orthogonal equipartition then we could iterate only over the sets \(A_1\subset X\) with \(\lvert A_1 \rvert=3\) to find the planes \(H_1\supset A_1\) which halve \(X\) (there are at most \(n^{5/2}\) SST2001?), project \(X\) onto \(H_1\) and solve the \(2\)-dimensional version of the problem on \(H_1\) (time \(O(n\log(n))\) [8]) which produces planes \(H_2,H_3\) orthogonal and orthogonal to \(H_3\). This is almost, but not quite, an equipartition, so we can check in time \(O(n)\) if it is.
A version of our algorithm has been implemented using SageMath [9].The reader can find it in https://github.com/XGEu2X/Grunbaum-3d-Partitions. The repository includes instructions on how to use it, our experiments and a couple of examples of point sets which both possess and lack orthogonal equipartitions.
4 Acknowledgments↩︎
We extend our heartfelt gratitude to Jeffrey Uhlmann for his invaluable discussions and for pointing out the wider interest this problem holds.
This work was supported by UNAM-PAPIIT project IN111923.
References↩︎
http://www.sagemath.org.