\hideLIPIcs

Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY 11201 USA and \urlhttps://engineering.nyu.edu/faculty/[email protected]://orcid.org/0000-0003-3110-4702Work has been supported by NSF grants CCF 15-40656 and CCF 20-08551, and by grant 2014/170 from the US-Israel Binational Science Foundation. Part of this research was conducted while BA was visiting ISTA in the summers of 2022 and 2023. The visit of BA to ISTA in the summer of 2022 was supported by an ISTA Visiting Professorship. Research of BA also partially supported by ERC grant no. 882971, “GeoScape,” and by the Erdős Center. School of Mathematics, Monash University, VIC 3800, Australia and \urlhttps://sites.google.com/view/[email protected]://orcid.org/0000-0003-0754-3203Work has been supported by Australian Research Council grant DP220102212. Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY 11201 [email protected]://orcid.org/0009-0008-9967-0819Work supported by a Tandon School of Engineering Fellowship and by NSF Grant CCF-20-08551. Institute of Science and Technology Austria, Am Campus 1, 3400 Klosterneuburg, Austria and \urlhttps://gtasinato.github.io/[email protected]://orcid.org/0009-0008-7231-5753 Institute of Science and Technology Austria, Am Campus 1, 3400 Klosterneuburg, Austria and \urlhttps://ist.ac.at/en/research/wagner-group/[email protected]://orcid.org/0000-0002-1494-0568 \CopyrightBoris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner \ccsdesc[100]Theory of computation $\to$ Randomness, geometry and discrete structures $\to$ Computational geometry \ccsdesc[100]Mathematics of computing $\to$ Discrete mathematics

Acknowledgements.

BA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work.

Eight-Partitioning Points in 3D, and Efficiently Too^†^†thanks: A preliminary version of this work will appear in SoCG’24 [3].

Boris Aronov Abdul Basit Indu Ramesh Gianluca Tasinato Uli Wagner

Abstract

An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in $\mathbb{R}^{3}$ consists of three planes that divide the space into $8$ octants, such that each open octant contains at most $1/8$ of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in $\mathbb{R}^{3}$ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument.

We prove the following variant of this result: Any mass distribution (or point set) in $\mathbb{R}^{3}$ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction.

Moreover, we present an efficient algorithm for calculating an eight-partition of a set of $n$ points in $\mathbb{R}^{3}$ (with prescribed normal direction of one of the planes) in time $O^{*}(n^{5/2})$ .

keywords:

Mass partitions, partitions of points in three dimensions, Borsuk-Ulam Theorem, Ham-Sandwich Theorem

category:

\relatedversion

1 Introduction

Geometric methods for partitioning space, point sets, or other geometric objects are a central topic in discrete and computational geometry. Partitioning results are often proved using topological methods and also play an important role in topological combinatorics [8, 17, 19, 22]. A classical example is the famous Ham-Sandwich Theorem, which goes back to the work of Steinhaus, Banach, Stone, and Tukey (see [19, Sec. 1] for more background and references). A “discrete” version of this theorem asserts that, given any $d$ finite point sets $P_{1},\dots,P_{d}$ in $\mathbb{R}^{d}$ , there is an (affine) hyperplane $H$ that simultaneously bisects all $P_{i}$ , i.e., each of the two open half-spaces determined by $H$ contains at most $|P_{i}|/2$ points, $1\leq i\leq d$ . This follows (by a standard limit argument, see [17, Sec. 3.1]) from the following “continuous” version: Let $\mu_{1},\dots,\mu_{d}$ be mass distributions in $\mathbb{R}^{d}$ , i.e., finite measures such that every open set is measurable and every hyperplane has measure zero. Then there exists a hyperplane $H$ such that $\mu_{i}(H^{+})=\mu_{i}(H^{-})=\frac{1}{2}\mu_{i}(\mathbb{R}^{d})$ for $1\leq i\leq d$ , where $H^{+}$ and $H^{-}$ are the two open half-spaces bounded by $H$ .

In this paper, we are interested in another classical equipartitioning problem, first posed by Grünbaum [11] in 1960: Given a mass distribution (respectively, a finite point set) in $\mathbb{R}^{d}$ , can one find $d$ hyperplanes that subdivide $\mathbb{R}^{d}$ into $2^{d}$ open orthants, each of which contains exactly $1/2^{d}$ of the mass (respectively, at most $1/2^{d}$ of the points)? We call such a $d$ -tuple of hyperplanes a $2^{d}$ -partition of the mass distribution (respectively, of the point set).

For $d=2$ , it is an easy consequence of the planar Ham-Sandwich theorem that any mass distribution (or point set) in $\mathbb{R}^{2}$ admits a four-partition; moreover, the four-partition can be chosen such that one of the lines has a prescribed direction (indeed, start by choosing a first line in the prescribed direction that bisects the given mass distribution; by the Ham-Sandwich Theorem, there exists a second line that simultaneously bisects the two parts of the mass on either side of the first line). Alternatively, one can also show that there is always a four-partition such that the two lines are orthogonal. Intuitively, the reason that we can impose such additional conditions is that the four-partitioning problem in the plane is underconstrained: A line in the plane can be described by two independent parameters, so a pair of lines have four degrees of freedom, while the condition that the four quadrants have the same mass can be expressed by three equations, leaving one degree of freedom; either one of the additional constraints uses this extra degree of freedom.

In 1966, Hadwiger [12] gave an affirmative answer to Grünbaum’s question for $d=3$ and showed that any mass distribution in $\mathbb{R}^{3}$ admits an eight-partition; moreover, the normal vector of one of the planes can be prescribed arbitrarily. This result was later re-discovered by Yao, Dobkin, Edelsbrunner, and Paterson [23].

Theorem 1.1 ([12, 23]).

Let $\mu$ be a mass distribution on $\mathbb{R}^{3}$ , and let $v\in\mathbb{S}^{2}$ . Then there exists a triple of planes $(H_{1},H_{2},H_{3})$ that form an eight-partition for $\mu$ and such that the normal vector of $H_{1}$ is $v$ .

More recently, Blagojević and Karasev [6] gave a different proof for the existence of eight-partitions and showed the following variant:

Theorem 1.2 ([6]).

Let $\mu$ be a mass distribution on $\mathbb{R}^{3}$ . Then there exists an eight-partition $(H_{1},H_{2},H_{3})$ of $\mu$ such that the plane $H_{1}$ is perpendicular to both $H_{2}$ and $H_{3}$ .

Our first result is the following alternative version of eight-partitioning, which to the best of our knowledge is new:

Theorem 1.3.

Given a mass distribution $\mu$ in $\mathbb{R}^{3}$ and a vector $v\in\mathbb{S}^{2}$ , there exists an eight-partition $(H_{1},H_{2},H_{3})$ of $\mu$ such that the intersection of the two planes $H_{1}$ and $H_{2}$ is a line in direction $v$ .

As in the case of the Ham-Sandwich Theorem, each of the three theorems above also implies the existence of the corresponding type of eight-partition for finite point sets, again by a standard limit argument (see Lemma A.1).

We remark that, in general, $d$ hyperplanes in $\mathbb{R}^{d}$ are described by $d^{2}$ independent parameters, while the condition that $2^{d}$ orthants have equal mass can be expressed by $2^{d}-1$ equations. For $d=3$ , this leaves $9-7=2$ degrees of freedom, which allows for any one of the additional conditions imposed in Theorems 1.1, 1.2, and 1.3, respectively. On the other hand, for $d\geq 5$ , we have $d^{2}<2^{d}-1$ , so intuitively Grünbaum’s problem is overconstrained. Avis [4] made this precise and constructed explicit counterexamples using the well-known moment curve $\gamma=\{(t,t^{2},\dots,t^{d})\colon t\in\mathbb{R}\}$ in $\mathbb{R}^{d}$ . The crucial fact is that any hyperplane intersects the moment curve $\gamma$ in at most $d$ points ([17, Lemma 1.6.4]). Thus, for $d\geq 5$ , a mass distribution supported on $\gamma$ admits no $2^{d}$ -partition because any $d$ hyperplanes intersect $\gamma$ in at most $d^{2}$ points, which subdivide $\gamma$ into at most $d^{2}+1$ intervals, hence there are always at least $2^{d}-d^{2}-1>0$ orthants that do not intersect $\gamma$ and hence contain no mass. The last remaining case $d=4$ of Grünbaum’s problem, i.e., the question whether any mass distribution in $\mathbb{R}^{4}$ admits a $16$ -partition by four hyperplanes, remains stubbornly open (see [5], [8, Conjecture 7.2], [17, pp. 50–51], and [19, Problem 2.1.4] for more background and related open problems).

We now turn to the algorithmic question of computing eight-partitions in $\mathbb{R}^{3}$ .

Problem 1.4.

Given a set $P$ of $n$ points in $\mathbb{R}^{3}$ , in sufficiently general position, compute three planes $H_{1},H_{2},H_{3}$ that form an eight-partition of the points.

As remarked above, the corresponding problem of computing a four-partition of a planar point can be reduced to finding a Ham-Sandwich cut of two planar point sets that are separated by a line; Megiddo [18] showed that this can be done in linear time.

Computing a Ham-Sandwich cut in $\mathbb{R}^{3}$ can be done efficiently, in time $O^{*}(n^{3/2})$ [16] (where $n$ is the total number of points and the $O^{*}(\cdot)$ -notation suppresses polylogarithmic factors). In general, the best known algorithm for computing Ham-Sandwich cuts in fixed dimension $d\geq 3$ runs in time $O(n^{d-1-\alpha_{d}})$ where $\alpha_{d}>0$ a constant depending only on $d$ [16], and a decision variant of the problem becomes computationally hard when the dimension is part of the input, see, e.g., [14]. However, the problem of computing eight-partitions in $\mathbb{R}^{3}$ seems significantly more difficult, and there is no known way of reducing it to the computation of a Ham-Sandwich cut; in particular, given two planes $H_{1}$ and $H_{2}$ that four-sect a finite point set $P$ (in the sense that every one of the four open orthants determined by $H_{1}$ and $H_{2}$ contains at most $|P|/4$ points), there generally need not exist a third plane $H_{3}$ such that $H_{1},H_{2},H_{3}$ form an eight-partition.

The following concept is useful for characterizing the complexity of Problem 1.4. A halving plane for an $n$ -point set for $n$ odd in $\mathbb{R}^{3}$ in general position is a plane that passes through three of the points and contains exactly $(n-3)/2$ points on each side. Let $h_{3}(n)$ be the maximum number of halving planes for an $n$ -point set $\mathbb{R}^{3}$ as above. The best known upper and lower bounds for $h_{3}(n)$ are $O(n^{5/2})$ and $\Omega(n^{2}e^{\sqrt{\log n}})$ , due to Sharir, Smorodinsky, and Tardos [20] and Tóth [21], respectively. A brute-force algorithm that checks every triple of halving planes solves Problem 1.4 in time roughly proportional to $(h_{3}(n))^{3}$ .

Yao et al. [23] and Edelsbrunner [9] gave a $O(n^{6})$ time algorithm for Problem 1.4 that computes an eight-partition (with a prescribed normal direction for one of the planes, as in Theorem 1.1) by an expensive search, using the fact that only two planes need to be identified. Fixing one plane and performing a brute-force search for the remaining two would yield an algorithm with a running time comparable to $(h_{3}(n))^{2}$ .

Here, we present, to our knowledge, the fastest known algorithm for Problem 1.4. Roughly speaking, our algorithm runs in time near-linear in $h_{3}(n)$ rather than quadratic in it.

Theorem 1.5 (Algorithm).

An eight-partition of $n$ points in general position in $\mathbb{R}^{3}$ , with a prescribed normal vector for one of the planes, can be computed in time $O^{*}(n^{5/2})$ ; the $O^{*}(\cdot)$ -notation suppresses polylogarithmic factors.

Our algorithm can be seen as a constructive version of Hadwiger’s proof [12]. We start by bisecting the point set by a plane with a fixed normal direction, which partitions the initial point set into two subsets of “red” and “blue” points, respectively, of equal size. After that, our algorithm finds two more planes that simultaneously four-sect both the red points and the blue points.

It remains an open question whether Theorem 1.2 or our own Theorem 1.3 can also be used to obtain an efficient algorithm for Problem 1.4. It would also be interesting to decide whether there is an algorithm for Problem 1.4 with running time $o(h_{3}(n))$ .

2 The topological result

2.1 Notation and preliminaries

In what follows, it will often be convenient to assume that the mass distributions we work with have connected support where the support of a mass distribution $\mu$ is $\operatorname{Supp}(\mu)\coloneqq\{x\in\mathbb{R}^{3}:\mu(B_{r}(x))>0\text{ for every }r>0\}$ and $B_{r}(x)$ denotes the ball of radius $r>0$ centred at $x$ . By a standard limit argument (see Lemma A.5), the existence of eight-partitions for mass distributions with connected support implies the existence of eight-partitions for the general case. Hereafter, unless stated otherwise, we assume, without loss of generality, that every mass distribution has connected support.

We denote the scalar product of two vectors $x,y\in\mathbb{R}^{3}$ by $x\cdot y\coloneqq\sum_{i=1}^{3}x_{i}y_{i}.$ A vector $v\in\mathbb{R}^{3}\setminus\{\mathbf{0}\}$ and a scalar $a\in\mathbb{R}$ determine an (affine) plane

H=H_{v}(a):=\{x\in\mathbb{R}^{3}:x\cdot v=a\},

together with an orientation of $H$ (given by the direction of the normal vector $v$ ). We denote by $-H:=H_{-v}(-a)$ the affine plane with the same equation as $H$ but with opposite orientation. The oriented plane $H$ determines two open half-spaces, denoted by

H^{+}:=\{x\in\mathbb{R}^{3}:x\cdot v>a\}\quad\text{and}\quad H^{-}:=\{x\in\mathbb{R}^{3}:x\cdot v<a\}.

More generally, let $\mathcal{H}=(H_{1},\dots,H_{k})$ be an ordered $k$ -tuple of (oriented) planes in $\mathbb{R}^{3}$ , $k\leq 3$ . In what follows, it will be convenient to identify the set $\{+,-\}$ with the group $\mathbb{Z}_{2}$ (where the group operation is multiplication of signs). Elements of $\{+,-\}^{k}=\mathbb{Z}_{2}^{k}$ are strings of signs of length $k$ , and we will denote by $\bm{+}=+\dots+$ the identity element of $\mathbb{Z}_{2}^{k}$ .

For $\alpha=(\alpha_{1},\dots,\alpha_{k})\in\mathbb{Z}_{2}^{k}=\{+,-\}^{k}$ , we define the open orthant determined by $\mathcal{H}$ and $\alpha$ as $\mathcal{O}_{\alpha}^{\mathcal{H}}:=H_{1}^{\alpha_{1}}\cap\dots\cap H_{k}^{\alpha_{k}}$ . Given a mass distribution $\mu$ in $\mathbb{R}^{3}$ , we say that an ordered $k$ -tuple $\mathcal{H}=(H_{1},\dots,H_{k})$ of planes ( $k\leq 3$ ) forms a $2^{k}$ -partition of $\mu$ if every orthant contains $1/2^{k}$ of the mass, i.e., $\mu(\mathcal{O}_{\alpha}^{\mathcal{H}})=\mu(\mathbb{R}^{3})/2^{k}$ for every $\alpha\in\{+,-\}^{k}$ . For $k=1,2,3$ , this corresponds to the notions of bisecting, four-secting, and eight-partitioning $\mu$ as mentioned in the introduction. Analogously, we say that $\mathcal{H}$ forms a $2^{k}$ -partition of a finite point set $P$ in $\mathbb{R}^{3}$ if $\lvert P\cap\mathcal{O}^{\mathcal{H}}_{\alpha}\rvert\leq\frac{\lvert P\rvert}{2^{k}}$ for all $\alpha$ .

We will parameterize oriented planes in $\mathbb{R}^{3}$ by $\mathbb{S}^{3}$ , where the north pole $e_{4}$ and the south pole $-e_{4}$ map to the plane at infinity with opposite orientations. For this we embed $\mathbb{R}^{3}$ into $\mathbb{R}^{4}$ via the map $(x_{1},x_{2},x_{3})\mapsto(x_{1},x_{2},x_{3},1).$ An oriented plane in $\mathbb{R}^{3}$ is mapped to an oriented affine $2$ -dimensional subspace of $\mathbb{R}^{4}$ and is extended (uniquely) to an oriented linear hyperplane. The unit normal vector on the positive side of the linear hyperplane defines a point on the sphere $\mathbb{S}^{3}$ . Hence, there is a one-to-one correspondence between points $v$ in $\mathbb{S}^{3}\setminus\{e_{4},-e_{4}\}$ and oriented affine planes $H_{v}$ in $\mathbb{R}^{3}$ . The positive side of the plane at infinity is $\mathbb{R}^{3}$ for $v=e_{4}$ and $\emptyset$ for $v=-e_{4}$ . Hence $H_{-v}^{+}=H_{v}^{-}$ for every $v$ . Note that planes at infinity cannot arise as solutions to the measure partitioning problem, since they produce empty orthants. Therefore we do not need to worry about the fact that the sphere includes these.

We parameterize triples of planes (called plane configurations) in $\mathbb{R}^{3}$ by $(\mathbb{S}^{3})^{3}$ , and denote by $\mathcal{H}_{v}$ the triple corresponding to $v\in(\mathbb{S}^{3})^{3}$ . Given a mass distribution $\mu$ on $\mathbb{R}^{3}$ , for each $v\in(\mathbb{S}^{3})^{3}$ and $\alpha\in\mathbb{Z}_{2}^{3}\setminus\{\bm{+}\}$ , we set

F_{\alpha}(v,\mu)=\sum_{\beta\in\mathbb{Z}_{2}^{3}}(-1)^{p(\alpha,\beta)}\mu(\mathcal{O}_{\beta}^{\mathcal{H}_{v}}).

where $p(\alpha,\beta)$ is the number of coordinates where both $\alpha$ and $\beta$ are $-$ . As an example, with $\mathcal{H}:=\mathcal{H}_{v}=(H_{1},H_{2},H_{3})$ and $\alpha=--+\in\mathbb{Z}_{2}^{3}\setminus\{\bm{+}\}$ , we obtain

	$\displaystyle F_{--+}(\mathcal{H},\mu)$	$\displaystyle=\sum_{\beta\in\mathbb{Z}_{2}^{3}}(-1)^{p(\alpha,\beta)}\mu(\mathcal{O}_{\beta}^{\mathcal{H}})=\sum_{\beta\in\mathbb{Z}_{2}^{3}:\,p(\alpha,\beta)=0}\mu(\mathcal{O}_{\beta}^{\mathcal{H}})-\sum_{\beta\in\mathbb{Z}_{2}^{3}:\,p(\alpha,\beta)=1}\mu(\mathcal{O}_{\beta}^{\mathcal{H}})$
		$\displaystyle=\left(\mu(\mathcal{O}^{\mathcal{H}}_{+++})+\mu(\mathcal{O}^{\mathcal{H}}_{++-})+\mu(\mathcal{O}^{\mathcal{H}}_{--+})+\mu(\mathcal{O}^{\mathcal{H}}_{---})\right)$
		$\displaystyle\quad-\left(\mu(\mathcal{O}^{\mathcal{H}}_{-++})+\mu(\mathcal{O}^{\mathcal{H}}_{-+-})+\mu(\mathcal{O}^{\mathcal{H}}_{+-+})+\mu(\mathcal{O}^{\mathcal{H}}_{+--})\right)$
		$\displaystyle=\mu(H_{1}^{+}\cap H_{2}^{+})+\mu(H_{1}^{-}\cap H_{2}^{-})-\mu(H_{1}^{-}\cap H_{2}^{+})-\mu(H_{1}^{+}\cap H_{2}^{-}).$

When $\mu$ is clear from context, we write $F_{\alpha}(\mathcal{H})$ instead of $F_{\alpha}(\mathcal{H},\mu)$ . The definitions of alternating sums for a pair of planes or a single plane are analogous.

The alternating sums have the following properties which will play an important role in the proof below. {observation} Let $\mu$ be a mass distribution and fix $k=2,3$ .

[(i)]
1.

Let $\alpha\in\mathbb{Z}_{2}^{k-1}\setminus\{\bm{+}\}$ and let $\mathcal{H}=(H_{1},\dots,H_{k})$ be a $k$ -tuple of planes, then $F_{+\alpha}(\mathcal{H})=F_{\alpha}((H_{2},\dots,H_{k}))$ (the equivalent statement holds for any other entry of a $k$ -tuple $\alpha_{1}\cdots\alpha_{k}$ instead of just for $\alpha_{1}$ ).
2.

A $k$ -tuple $\mathcal{H}$ of planes $2^{k}$ -partitions if and only if $F_{\alpha}(\mathcal{H})=0$ for every $\alpha\in\mathbb{Z}_{2}^{k}\setminus\{\bm{+}\}$ .

Proof 2.1.

(1) Since every hyperplane has null measure it follows that, for any $\beta\in\mathbb{Z}_{2}^{k-1}$

\mu(\mathcal{O}^{\mathcal{H}}_{\beta})=\mu(\mathcal{O}^{\mathcal{H}}_{+\beta})+\mu(\mathcal{O}^{\mathcal{H}}_{-\beta}).

From the definition of $F_{\tilde{\alpha}}$ , if $\tilde{\alpha}=+\alpha$ then for any $\beta\in\mathbb{Z}_{2}^{k-1}$ the two orthants $\mathcal{O}^{\mathcal{H}}_{+\beta}$ and $\mathcal{O}^{\mathcal{H}}_{-\beta}$ are counted with the same sign in the sum, therefore

F_{\tilde{\alpha}}(\mathcal{H})=\sum_{\begin{subarray}{c}\beta\in\mathbb{Z}_{2}^{k-1}\\ p(\alpha,\beta)=0\end{subarray}}\left(\mu(\mathcal{O}^{\mathcal{H}}_{+\beta})+\mu(\mathcal{O}^{\mathcal{H}}_{-\beta})\right)-\sum_{\begin{subarray}{c}\beta\in\mathbb{Z}_{2}^{k-1}\\ p(\alpha,\beta)=1\end{subarray}}\left(\mu(\mathcal{O}^{\mathcal{H}}_{+\beta})+\mu(\mathcal{O}^{\mathcal{H}}_{-\beta})\right)=F_{\alpha}(\left(H_{2},\dots,H_{k}\right)).

(2) It is clear that, if $\mathcal{H}$ is a $2^{k}$ -partition, then all the alternating sums are $0$ . We will prove the other implication.

Suppose first that $k=1$ and that $\mathcal{H}=H$ . The only alternating sum is $F_{-}(H)=\mu(H^{+})-\mu(H^{-})$ and $F_{-}(H)=0$ implies that $H$ bisects.

Suppose now that $k=2$ and that $\mathcal{H}=(H_{1},H_{2})$ . By (1) and the statement for a single plane, $F_{+-}(\mathcal{H})=0$ and $F_{-+}(\mathcal{H})=0$ imply that both $H_{1}$ and $H_{2}$ bisect. Therefore, if $\lambda\coloneqq\mu(\mathcal{O}^{\mathcal{H}}_{++})$ , we have that

0=F_{--}(\mathcal{H})=\mu(\mathcal{O}^{\mathcal{H}}_{++})+\mu(\mathcal{O}^{\mathcal{H}}_{--})-\mu(\mathcal{O}^{\mathcal{H}}_{-+})-\mu(\mathcal{O}^{\mathcal{H}}_{+-})=\lambda+\lambda-(\frac{1}{2}-\lambda)-(\frac{1}{2}-\lambda)=4\lambda-1;

hence $\lambda=\frac{1}{4}$ as desired.

Finally, suppose that $k=3$ and that $\mathcal{H}=(H_{1},H_{2},H_{3})$ . By (1) and the statement for single planes and for pairs of planes, we have that all planes $H_{i}$ bisect and all pairs $(H_{i},H_{j})$ four-partition. Therefore, if $\lambda\coloneqq\mu(\mathcal{O}^{\mathcal{H}}_{+++})$ , we have that

	$\displaystyle 0=F_{---}(\mathcal{H})$	$\displaystyle=\mu(\mathcal{O}^{\mathcal{H}}_{+++})+\mu(\mathcal{O}^{\mathcal{H}}_{+--})+\mu(\mathcal{O}^{\mathcal{H}}_{-+-})+\mu(\mathcal{O}^{\mathcal{H}}_{--+})$
		$\displaystyle\quad-\mu(\mathcal{O}^{\mathcal{H}}_{-++})-\mu(\mathcal{O}^{\mathcal{H}}_{+-+})-\mu(\mathcal{O}^{\mathcal{H}}_{++-})-\mu(\mathcal{O}^{\mathcal{H}}_{---})$
		$\displaystyle=\lambda+\lambda+\lambda+\lambda-(\frac{1}{4}-\lambda)-(\frac{1}{4}-\lambda)-(\frac{1}{4}-\lambda)-(\frac{1}{4}-\lambda)=8\lambda-1;$

hence $\lambda=\frac{1}{8}$ as claimed.

2.2 The main topological result

Our goal is to prove the following result — a more precise statement of Theorem 1.3:

Theorem 2.2.

Given a mass distribution $\mu$ and a direction $p\in\mathbb{S}^{2}$ , there exists a triple $\mathcal{H}=(H_{1},H_{2},H_{3})$ of oriented planes that eight-partition $\mu$ so that the oriented direction of the intersection $H_{1}\cap H_{2}$ is $p$ .

By Lemma A.5, it is sufficient to prove Theorem 2.2 for mass distributions with connected support. We require the following technical lemma about partitioning a mass distribution on $\mathbb{R}^{2}$ , due to Blagojević and Karasev [6]. For completeness, the proof is given in Appendix C. {restatable}[Four-partitioning a mass distribution in $\mathbb{R}^{2}$ [6]]lemmablagkarasev Let $\mu^{\#}$ be a mass distribution (with connected support) on $\mathbb{R}^{2}$ and $v\in\mathbb{S}^{1}$ . Then there exists a pair $(\ell_{1},\ell_{2})$ of lines in $\mathbb{R}^{2}$ that four-partitions $\mu^{\#}$ and such that $v$ bisects the angle between $\ell_{1}$ and $\ell_{2}$ .

Moreover, if we orient $\ell_{1}$ and $\ell_{2}$ so that $\ell_{1}$ is in the first direction clockwise from $v$ , and $\ell_{2}$ is in the first direction counterclockwise, the oriented pair is unique and the lines depend continuously on $v$ .

Proof 2.3 (Proof of Theorem 2.2).

Without loss of generality, let $v=(0,0,1)$ . Our proof proceeds in two steps. In the first step, we construct a map $\Phi\colon\mathbb{S}^{1}\times\mathbb{S}^{3}\rightarrow\mathbb{R}^{4}$ whose zeros codify equipartitions of $\mu$ ; then we prove that $\Phi$ is equivariant with respect to a suitable choice of actions of $G:=\mathbb{Z}_{4}\times\mathbb{Z}_{2}$ on the two spaces. In the second step we show that any continuous $G$ -equivariant map $\Psi\colon\mathbb{S}^{1}\times\mathbb{S}^{3}\rightarrow\mathbb{R}^{4}$ has to have a zero.

Step 1: The key step in constructing the map $\Phi$ is to show that we can parameterize pairs of planes that have intersection direction $p$ and four-sect $\mu$ , by a vector in $\mathbb{S}^{1}$ .

We project $\mu$ to the $xy$ -plane to obtain a mass distribution $\mu^{\#}$ on $\mathbb{R}^{2}$ . Lemma 2.2 guarantees that, once we fix a direction $v\in\mathbb{S}^{1}\hookrightarrow\mathbb{S}^{2}$ (inclusion as the horizontal equator in $\mathbb{S}^{2}$ ) there are two lines in the $xy$ -plane $\ell_{1}=\mathbb{R}\vec{\ell}_{1}(v)+a_{0}(v)$ and $\ell_{2}=\mathbb{R}\vec{\ell}_{2}(v)+a_{2}(v)$ that four-sect the projected measure $\mu^{\#}$ . Define $H_{i}(v)\coloneqq(h_{i}(v),a_{i}(v))$ to be the (oriented) span of $\ell_{i}(v)$ and $v$ ; the two planes now four-sect $\mu$ and have the desired intersection direction.

Now let $g_{1}$ be a generator of $\mathbb{Z}_{4}\times\{\bm{+}\}\subseteq G$ and define its action on $\mathbb{S}^{1}$ by a counterclockwise rotation by $\frac{\pi}{2}$ . We use $g_{1}\cdot v$ to denote the action of $g_{1}$ on $v$ . Then, by the uniqueness in Lemma 2.2, we have that

\vec{\ell}_{1}(g_{1}\cdot v)=\vec{\ell}_{2}(v)\quad\text{and}\quad\vec{\ell}_{2}(g_{1}\cdot v)=-\vec{\ell}_{1}(v).

(1)

Intuitively, if we consider the planar problem with the bisecting vector $v$ rotated by $\frac{\pi}{2}$ , by uniqueness the affine lines that split the measure are the same. However, while the direction chosen as $\vec{\ell}_{1}$ in the rotated problem is the direction $\vec{\ell}_{2}$ in the previous configuration, the “rotated” $\vec{\ell}_{2}$ is $-\vec{\ell}_{1}$ in the original problem (see Figure 1).

Refer to caption — Figure 1: Example of the action of $g_{1}$ .

Using this construction, we can define a function $\mathbb{S}^{1}\rightarrow\mathbb{S}^{3}\times\mathbb{S}^{3}$ by $v\mapsto(H_{1}(v),H_{2}(v))$ . It follows from eq. (1) that $g_{1}\cdot v$ is mapped to $(H_{2}(v),-H_{1}(v))$ , therefore, if we fix the corresponding action¹¹1Formally, for any $(x,y)\in\mathbb{S}^{3}\times\mathbb{S}^{3}$ the generator $g_{1}$ of $\mathbb{Z}_{4}\times\{+\}\subseteq G$ acts by $g_{1}\cdot(x,y)=(y,-x)$ . of $\mathbb{Z}_{4}$ on $\mathbb{S}^{3}\times\mathbb{S}^{3}$ , the map is $\mathbb{Z}_{4}$ -equivariant.

The group $\{e\}\times\mathbb{Z}_{2}$ acts by antipodality on $\mathbb{S}^{3}$ ; therefore, if $G$ acts on $\left(\mathbb{S}^{3}\times\mathbb{S}^{3}\right)\times\mathbb{S}^{3}$ component-wise, the map $\Phi\colon\mathbb{S}^{1}\times\mathbb{S}^{3}\to\left(\mathbb{S}^{3}\times\mathbb{S}^{3}\right)\times\mathbb{S}^{3}$ defined as $\Phi(v,w)\coloneqq(H_{1}(v),H_{2}(v),w)$ is $G$ -equivariant.

By construction, the first two planes are always a four-partition of the mass distribution, therefore by Observation 2.1, a configuration $\Phi(v,w)$ is an eight-partition if and only if the four alternating sums with $\alpha_{3}=-$ (i.e., $\alpha=++-$ , $-+-$ , $+--$ and $---$ ) are $0$ .

To compute the action of $G$ on the alternating sums, it is enough to specify what happens on $g_{1}$ (a generator of $\mathbb{Z}_{4}\times\{e\}$ ) and $g_{2}$ (a generator of $\{e\}\times\mathbb{Z}_{2}$ ). If we act with $g_{1}$ , we obtain

	$\displaystyle F_{++-}(g_{1}\cdot\Phi(v,w))$	$\displaystyle=F_{++-}(\Phi(v,w)),$
	$\displaystyle F_{+--}(g_{1}\cdot\Phi(v,w))$	$\displaystyle=-F_{-+-}(\Phi(v,w)),$
	$\displaystyle F_{-+-}(g_{1}\cdot\Phi(v,w))$	$\displaystyle=F_{+--}(\Phi(v,w)),\text{ and}$
	$\displaystyle F_{---}(g_{1}\cdot\Phi(v,w))$	$\displaystyle=-F_{---}(\Phi(v,w)),$

while acting with $g_{2}$ produces

	$\displaystyle F_{++-}(g_{2}\cdot\Phi(v,w))$	$\displaystyle=-F_{++-}(\Phi(v,w)),$
	$\displaystyle F_{+--}(g_{2}\cdot\Phi(v,w))$	$\displaystyle=-F_{-+-}(\Phi(v,w)),$
	$\displaystyle F_{-+-}(g_{2}\cdot\Phi(v,w))$	$\displaystyle=-F_{+--}(\Phi(v,w)),\text{ and}$
	$\displaystyle F_{---}(g_{2}\cdot\Phi(v,w))$	$\displaystyle=-F_{---}(\Phi(v,w)),$

for every $\left(v,w\right)\in\mathbb{S}^{1}\times\mathbb{S}^{3}$ .

Finally, we can choose a linear $G$ -action on $\mathbb{R}^{4}$ that is consistent with the previous equations. In particular, if we define

g_{1}\cdot(x,y,z,u)=(x,-z,y,-u)\quad\text{and}\quad g_{2}\cdot(x,y,z,u)=(-x,-y,-z,-u),

then the map $\Psi\colon\mathbb{S}^{1}\times\mathbb{S}^{3}\rightarrow\mathbb{R}^{4}$ , given by

(v,w)\mapsto\left(F_{++-}(v,w),F_{+--}(v,w),F_{-+-}(v,w),F_{---}(v,w)\right)

is $G$ -equivariant. By Observation 2.1, the zeros of $\Psi$ are exactly the configurations of planes that eight-partition the measure and have the desired intersection property.

Step 2: Suppose now, for a contradiction, that $\Psi$ does not have a zero. This means that it is possible to define a $G$ -equivariant map $\overline{\Psi}\colon\mathbb{S}^{1}\times\mathbb{S}^{3}\rightarrow\mathbb{S}^{3}$ by $\overline{\Psi}(v,w)\coloneqq\frac{\Psi(v,w)}{\lVert\Psi(v,w)\rVert}$ .

Denote by $\Psi_{a}$ , for $a\in\mathbb{S}^{1}$ , the map $\Psi_{a}\colon\mathbb{S}^{3}\rightarrow\mathbb{S}^{3}$ , $\Psi_{a}(p)=\overline{\Psi}(a,p)$ ; this function has two key properties:

[(i)]
1.

for any $a\in\mathbb{S}^{1}$ , $\Psi_{a}$ is antipodal;
2.

for any $a,b\in\mathbb{S}^{1}$ , $\Psi_{a}$ and $\Psi_{b}$ are homotopic.

However, the map induced by $g_{1}$ on the sphere has degree $-1$ by Proposition B.1 and thus we have

[\Psi_{a}]=[\Psi_{g_{1}\cdot a}]=[g_{1}\cdot\Psi_{a}]=-[\Psi_{a}].

Hence $\Psi_{a}$ is null-homotopic, contradicting Proposition B.3.

Theorem 2.2, along with Lemma A.1, immediately implies the following.

Theorem 2.4.

Let $P\subseteq\mathbb{R}^{3}$ be a finite set of points and $p\in\mathbb{S}^{2}$ a fixed direction. Then there exists a triple $\mathcal{H}=(H_{1},H_{2},H_{3})$ of oriented planes that eight-partitions $P$ , so that the oriented direction of the intersection $H_{1}\cap H_{2}$ is $p$ .

3 Levels in arrangements of planes

Let $P\subseteq\mathbb{R}^{3}$ be a set of $n$ points in general position. Specifically, we assume that the points in $P$ satisfy the following: no four in a plane, no three in a vertical plane, and no two in a horizontal plane. Recall that a halving plane for an $n$ -point set (with $n$ odd) in $\mathbb{R}^{3}$ in general position is a plane that passes through three of the points and contains exactly $(n-3)/2$ points on each side, and that $h_{3}(n)$ is the maximum number of halving planes for an $n$ -point set in $\mathbb{R}^{3}$ .

Let $H$ be a set of planes in $\mathbb{R}^{3}$ in general position. Specifically, we assume that the planes are non-vertical, every triple of planes in $H$ meets in a unique point, and no point in $\mathbb{R}^{3}$ is incident with more than three of the planes. The planes in $H$ partition $\mathbb{R}^{3}$ into a complex of convex cells, called the arrangement of $H$ and denoted by $\mathcal{A}(H)$ . The $k$ -level in $\mathcal{A}(H)$ is defined as the closure of the set of all points which lie on a unique plane of the arrangement and have exactly $k-1$ planes below it. Note that the $k$ -level is a piecewise linear surface in $\mathbb{R}^{3}$ whose faces are contained in planes of $H$ . When $k=\lfloor(|H|+1)/2\rfloor$ , the $k$ -level is called the median level of the arrangement.

Let $g_{3}(n)$ be the maximum complexity of any $k$ -level in an arrangement of $n$ planes in $\mathbb{R}^{3}$ . Using the standard duality transform²²2The duality transform maps points in $\mathbb{R}^{3}$ to planes in $\mathbb{R}^{3}$ and vice versa. Specifically, the point $p=(p_{1},p_{2},p_{3})\in\mathbb{R}^{3}$ is mapped to the non-vertical plane $p^{*}\colon z=p_{1}x+p_{2}y-p_{3}$ in $\mathbb{R}^{3}$ , and vice versa. See [13, Chapter 25.2] for standard properties of the duality transform., it is easily seen that $h_{3}(n)\leq g_{3}(n)$ ; indeed, the dual of a halving plane of $P$ is a vertex of the median level of the arrangement of $P^{*}=\{p^{*}:p\in P\}$ . It is a well-known fact that $h_{3}(n)=\Theta(g_{3}(n))$ (see [2, Theorem 3], [10, Theorem 3.3]).

The main object of interest in bounding the complexity of our algorithm is the intersection of median levels of two arrangements of disjoint sets of planes. We show that the complexity of this is proportional to $h_{3}(n)$ .

Fact 1.

Let $\ell(n)$ be the maximum complexity of the intersection of the median levels of the arrangements $\mathcal{A}(R)$ and $\mathcal{A}(B)$ of disjoint sets of planes $R$ and $B$ in $\mathbb{R}^{3}$ in general position, with $|R|=|B|=n$ and $n$ odd. Then $\ell(n)=\Theta(h_{3}(n))$ in the worst case.

Proof 3.1.

Suppose $n\coloneqq 2k+1$ . Let $L$ be the intersection of the median levels of $\mathcal{A}(R)$ and $\mathcal{A}(B)$ . As $R\cup B$ are in general position, $L$ is a collection of edges and vertices in $\mathcal{A}(R\cup B)$ . Note that $L$ is a collection of cycles and bi-infinite curves, in general, so its complexity is asymptotically determined by the number of its edges.

Each point on an edge of $L$ has the property that there are $2k$ planes of $R\cup B$ above it and $2k$ planes of $R\cup B$ below it. Hence $L$ is contained in the $2k$ -level of $\mathcal{A}(R\cup B)$ . It follows that the complexity of $L$ is bounded above by the complexity of a level in an arrangement of $n$ planes, implying $\ell(n)\leq g_{3}(2n)=O(h_{3}(n))$ . This proves the upper bound.

For the lower bound, let $P\subseteq\mathbb{R}^{3}$ be a set $n$ points in general position achieving the maximum number $h_{3}(n)$ of halving planes. Let $P^{\prime}$ be a copy of $P$ translated by a small $\varepsilon>0$ in a generic direction. We then slightly perturb the points of $P\cup P^{\prime}$ to ensure general position. For a point $p\in P$ , we denote by $p^{\prime}$ its copy in $P^{\prime}$ . Consider the sets $R^{*}$ (red) and $B^{*}$ (blue) of $n$ points obtained as follows: for each pair $(p,p^{\prime})$ , we assign one point to $R^{*}$ and the other to $B^{*}$ uniformly and independently at random.

Let $(a,b,c)$ be a triple of points of $P$ defining a halving plane, and consider the six points $S=(a,b,c,a^{\prime},b^{\prime},c^{\prime})$ . We claim that, with constant probability, there exists a plane $\pi$ that passes through one red point and one blue point and has precisely one red and one blue point on each side, from $S$ . As our perturbation $\varepsilon$ was arbitrarily small, $\pi$ partitions the remaining points of $R^{*}\cup B^{*}$ is the same manner is it partitions $P$ . Let $R$ and $B$ be the sets of planes dual to points in $R^{*}$ and $B^{*}$ , respectively. In the dual, the plane $\pi$ corresponds to a point $\pi^{*}$ on an edge of the intersection $L$ of the median levels of $\mathcal{A}(R)$ and $\mathcal{A}(B)$ : $\pi^{*}$ has $k$ red and $k$ blue planes lying above and below it, and lies on the intersection of exactly one red and one blue plane. Since different triples $(a,b,c)$ correspond to partitioning $P$ in different ways, the points $\pi^{*}$ arising from different halving planes $\pi$ lie on different edges of $L$ . By construction, the number of such edges is a constant fraction of $h_{3}(n)$ in expectation, completing the lower bound proof.³³3In our application, the sets of points $R^{*}$ and $B^{*}$ are separated, which is not the case in the above lower bound construction. With this additional constraint, it is possible that the complexity of $L$ is always $o(h_{3}(n))$ .

4 The algorithm

We can deduce the existence of eight-partitions of a finite point set $P\subset\mathbb{R}^{3}$ of a certain advantageous form from Theorem 1.1.

{observation}

Let $k>0$ be an integer and $P\subseteq\mathbb{R}^{3}$ be a set of $n=8k+7$ points in general position. Then, there exists a triple of planes $(H_{1},H_{2},H_{3})$ that eight-partitions $P$ with the following properties:

[(i)]
1.

$H_{1}$ is horizontal (i.e., parallel to the $xy$ -plane) and passes through the $z$ -median point of $P$ . From here on, we refer to the $4k+3$ points that lie below (resp., above) $H_{1}$ as red (resp., blue) points and denote the sets $R$ (resp. $B$ ).
2.

$H_{2}$ and $H_{3}$ each contain exactly three points, and each open octant contains exactly $k$ points.
3.

$H_{2},H_{3}$ each bisect $R$ and $B$ , and the pair $(H_{2},H_{3})$ four-partitions both $R$ and $B$ . Furthermore, $H_{2}$ and $H_{3}$ contain at least one point of each color.

Proof 4.1.

Since the set $X\coloneqq\{(H_{1},H_{2},H_{3}):H_{1}\text{ is horizontal}\}\subset(\mathbb{S}^{3})^{3}$ is compact, by Theorem 1.1 and Lemma A.1, there exists a configuration $\mathcal{H}_{\infty}=(H_{1},H_{2},H_{3})$ that eight-partitions the point set with $H_{1}$ horizontal. Along with the general position assumption, this implies that $H_{1}$ contains only the $z$ -median point. This proves (1).

To see (2), note that any eight-partition has at most $k$ points of $P$ in each of the eight open octants, one point in $H_{1}$ , and at most three points in each of $H_{2}$ and $H_{3}$ , by general position, for a total of at most $8k+1+2\cdot 3=8k+7=n$ points. So, in fact, all the inequalities are equalities: there must be exactly $k$ points in each open quadrant and exactly three points of $R\cup B$ in each of $H_{2}$ and $H_{3}$ .

It remains to show (3). By preceding paragraph, it is straightforward that $(H_{2},H_{3})$ four-partitions both $R$ and $B$ . By Corollary A.3, we have that any pair $(H_{i},H_{j})$ four-partitions $P$ . Since $(H_{1},H_{2})$ four-partitions $P$ , each quadrant formed by $(H_{1},H_{2})$ has at most $(8k+7)/4=2k+1$ points. $H_{1}$ has $4k+3$ points on each side. Hence, we obtain that $H_{2}$ bisects $R$ and $B$ , and, in particular, contains at least one point of each color. A symmetric argument shows that $H_{3}$ bisects both $R$ and $B$ , and contains at least one point of each color. This completes the proof.

Theorem 4.2 (Computation of an eight-partition).

Let $P\subseteq\mathbb{R}^{3}$ be a set of $n>0$ points in general position and $v\in\mathbb{S}^{2}$ . An eight-partition $(H_{1},H_{2},H_{3})$ of $P$ with $v$ being the normal vector of $H_{1}$ can be computed in time $O^{*}(n+m)$ , where $m$ is the maximum complexity of the intersection of the median levels of two sets of $n/2$ planes.

{remark*}

Since $m=O(h_{3}(n))=O(n^{5/2})$ by Fact 1, we can compute an eight-partition in time $O^{*}(n^{5/2})$ . The rest of this section is devoted to the proof of Theorem 4.2. We assume, without loss of generality, that $v=e_{3}=(0,0,1)$ is the vertical vector, so $H_{1}$ is required to be horizontal. If $n\leq 7$ , the statement holds trivially — set $H_{1}$ to be the horizontal plane containing any point of $P$ , and $H_{2},H_{3}$ to contain at most three distinct points each, so that the octants do not contain any points. From here on, we will assume that $n=8k+7$ , for an integer $k>0$ . If $n$ is not of this form, we may add dummy points to $P$ (in general position) until the number of points is of the required form and run the algorithm. Once the algorithm terminates, we discard the dummy points, resulting in an eight-partition with at most $k$ points in each octant.

We now describe the algorithm to construct an eight-partition of $P$ satisfying the properties in Observation 4. Let $H_{1}$ be the horizontal plane containing the $z$ -median point of $P$ , and, without loss of generality, identify $H_{1}$ with the $xy$ -plane. Now consider the sets $R$ and $B$ of $4k+3$ points each lying below and above, respectively, $H_{1}$ . We further assume, without loss of generality, that $B$ is contained in the half-space $x<0$ and $R$ is contained in the half-space $x>0$ . Otherwise, since no point in $R\cup B$ has $z=0$ by the general position assumption, there exists a plane $H$ containing the $y$ -axis and with sufficiently small negative slope in the $x$ direction such that all red points are below $H$ and all blue points are above $H$ . Applying a generic sheer transformation (so as not to violate the general position assumption) that fixes the $xy$ -plane and maps $H$ to the plane $x=0$ , we obtain point sets with the required properties.

Let $R^{*}=\{p^{*}:p\in R\}$ be the set of red planes dual to points in $R$ and set $\mathcal{A}(R):=\mathcal{A}(R^{*})$ to be the arrangement formed by the set $R^{*}$ . The set of blue planes $B^{*}$ and the blue arrangement $\mathcal{A}(B)$ are defined analogously. We will write $\mathcal{A}\coloneqq\mathcal{A}(R\cup B)$ for the arrangement formed by the planes in $R^{*}\cup B^{*}$ . For a (dual) point $p\in\mathbb{R}^{3}$ , we set $R^{+}_{p},R^{-}_{p}\subseteq R^{*}$ to be the set of red planes lying strictly above and below $p$ , respectively. For a pair $p,q$ of (dual) points, put

X(p,q)\coloneqq|R^{+}_{p}\cap R^{+}_{q}|-|R^{+}_{p}\cap R^{-}_{q}|-|R^{-}_{p}\cap R^{+}_{q}|+|R^{-}_{p}\cap R^{-}_{q}|.

The sets $B^{+}_{p},B^{-}_{p}\subseteq B^{*}$ and the function $Y(p,q)$ are defined analogously for $B^{*}$ .

Let $L$ be the intersection of the median levels of $\mathcal{A}(B)$ and $\mathcal{A}(R)$ . By the following lemma, we have that $L$ is a connected $y$ -monotone polygonal curve and is an alternating sequence of edges and vertices of $\mathcal{A}$ terminated by half-lines.

Lemma 4.3.

$L$ is a connected $y$ -monotone curve.

Proof 4.4.

Recall that $B$ lies in the quadrant $x<0,z<0$ and $R$ lies in the quadrant $x>0,z>0$ . Hence, the dual planes in $B^{*}$ and $R^{*}$ have equations of the form $z=ax+by+c$ with $a<0$ and $a>0$ , respectively.

Consider the intersection of $R^{*}\cup B^{*}$ with the plane $\Pi_{d}\colon y=d$ . The intersection of the plane $z=ax+by+c$ is the line $z=ax+(bd+c)$ , so planes in $B^{*}$ correspond to lines with negative slope and planes in $R^{*}$ correspond to lines with positive slope. In particular, the median levels of lines corresponding to $B^{*}$ and $R^{*}$ are graphs of piecewise-linear total functions that are decreasing and increasing, respectively. It follows that the two curves intersect exactly once. This intersection point corresponds to the intersection of $L$ with the plane $\Pi_{d}$ .

By general position, $L$ is a union of vertex-disjoint cycles and bi-infinite paths composed of edges and vertices of $\mathcal{A}$ , since incident to every vertex of $A$ contained in $L$ are precisely two edges belonging to $L$ . By monotonicity in $y$ , $L$ must be a single bi-infinite chain.

In fact, $L$ can be computed efficiently using standard tools [1, 7], which we outline now.

Lemma 4.5 (Computing the intersection of two levels [1, 7]).

The intersection curve $L$ of the median level of $\mathcal{A}(B)$ and the median level of $\mathcal{A}(R)$ can computed in time $O^{*}(n+m)$ , where $m$ is the complexity of the curve and $O^{*}(\cdot)$ notation hides polylogarithmic factors.

Proof 4.6.

We use the standard dynamic data structure for ray-shooting queries in the intersection of half-spaces; the currently fastest algorithm is due to Chan [7], see also earlier work of Agarwal and Matoušek [1].

A starting ray of $L$ can be computed by computing the intersection of the median levels in the vertical plane $\Pi_{d}\colon y=d$ for a small enough $d$ , defined as in the proof of Lemma 4.3, in linear time, using an algorithm of Megiddo [18].

Consider a point $p$ on the initial edge of $L$ (infinite in the $-y$ -direction). It lies on one plane of $\pi\in B$ and one plane $\pi^{\prime}\in R$ . Let $\ell$ be the intersection line of $\pi$ and $\pi^{\prime}$ , and consider the half line $\rho$ of $\ell$ starting at $p$ and infinite in the $+y$ -direction. The planes of $B\cup R$ (besides $\pi$ and $\pi^{\prime}$ ) are classified into those lying above $p$ and those lying below it. Call the first set $U$ and the second $D$ . We preprocess the intersection of the set of lower half-spaces defined by the planes of $U$ and the intersection of the set of upper half-spaces defined by the planes of $D$ for dynamic ray shooting and shoot with $\rho$ . The earlier of the two intersections identifies the first plane $\pi_{2}$ of $(B\cup R)\setminus\{\pi,\pi^{\prime}\}$ that $\rho$ meets. This is the next vertex of $\mathcal{A}(B\cup R)$ on $L$ ; $L$ turns here. If $\pi_{2}$ belongs to $B$ , $L$ now follows the intersection line of $\pi_{2}$ and $\pi^{\prime}$ . Otherwise it follows the intersection line of $\pi$ and $\pi_{2}$ . Past the intersection, the sets $U$ and $D$ need to be updated and we continue, following the next ray, until we trace all of $L$ .

The only cost besides the initial computation of $p$ are identifying $U$ and $D$ in $O(n)$ time, initializing the dynamic structure, in $O^{*}(n)$ time, and performing two ray shots and $O(1)$ updates on $U$ and $D$ per vertex of $L$ , each at a cost of $O^{*}(1)$ .

{note*}

As we construct $L$ , we can store it as a sequence of vertices and edges. Each edge is associated with the red-blue pair of planes containing it. An endpoint of an edge is contained in an additional plane. For each consecutive edge/vertex pair $(e,v)$ , in either direction, we record which new plane contains $v$ together with its color.

We now return to the computation of the eight-partition $(H_{1},H_{2},H_{3})$ . By the general position assumption, $H_{2}$ and $H_{3}$ cannot be vertical, so $H_{2}$ and $H_{3}$ correspond to vertices in $\mathcal{A}$ , by Observation 4. With the above setup, we can reformulate the problem of computing $H_{2}$ and $H_{3}$ as follows.

Claim 2 (The dual alternating sign functions).

Computing $H_{2}$ and $H_{3}$ is equivalent to identifying a pair of vertices $p,q\in L$ such that $Y(p,q)=X(p,q)=0$ .

Proof 4.7.

By Observation 4(2), the eight-partition $(H_{1},H_{2},H_{3})$ has exactly $k$ points in each of the eight open octants. Setting $p\coloneqq H_{2}^{*}$ and $q\coloneqq H_{3}^{*}$ , we obtain that $|R^{\pm}_{p}\cap R^{\pm}_{q}|=|B^{\pm}_{p}\cap B^{\pm}_{q}|=k$ for all combinations of signs. Therefore $Y(p,q)=X(p,q)=0$ , as claimed.

We now argue the other direction. Let $p,q\in L$ be vertices such that $X(p,q)=Y(p,q)=0$ . Since $p$ and $q$ lie on $L$ , $H_{2}\coloneqq p^{*}$ and $H_{3}\coloneqq q^{*}$ bisect both $R$ and $B$ and contain exactly three points each, at least one of each color. Hence, it suffices to show that $(H_{2},H_{3})$ is a four-partition of both $R$ and $B$ , i.e., $|R_{p}^{\pm}\cap R_{q}^{\pm}|,|B_{p}^{\pm}\cap B_{q}^{\pm}|\leq k$ for all combinations of signs. Indeed, this implies that each octant formed by $(H_{1},H_{2},H_{3})$ , contains exactly $k$ points completing the proof.

Let $a_{r}\coloneqq|R^{+}_{p}\cap R^{+}_{q}|$ , $b_{r}\coloneqq|R^{+}_{p}\cap R^{-}_{q}|$ , $c_{r}\coloneqq|R^{-}_{p}\cap R^{+}_{q}|$ , and $d_{r}\coloneqq|R^{-}_{p}\cap R^{-}_{q}|$ . Define $a_{b},b_{b},c_{b},d_{b}$ analogously for the blue planes. Without loss of generality, for a contradiction, suppose $a_{r}>k$ .

We first consider the case $a_{r}\geq k+2$ . Since $p$ lies on the median level of $\mathcal{A}(R)$ , we have $a_{r}+b_{r}\leq|R_{p}^{+}|=2k+1$ , implying $b_{r}\leq k-1$ . Similarly, since $q$ lies on the median level of $\mathcal{A}(R)$ , we have $c_{r}\leq k-1$ . Recall that, by assumption, $X(p,q)=a_{r}+d_{r}-b_{r}-c_{r}=0$ , implying $d_{r}=b_{r}+c_{r}-a_{r}\leq k-4$ . Hence, $a_{r}+b_{r}+c_{r}+d_{r}\leq 4k-4$ , so $p$ and $q$ together are contained in $4k+3-(a_{r}+b_{r}+c_{r}+d_{r})\geq 7$ red planes, contradicting the general position assumption.

We may now assume $a_{r}=k+1$ . Following the same reasoning we obtain $b_{r}\leq k$ , $c_{r}\leq k$ , and $d_{r}=b_{r}+c_{r}-a_{r}\leq k-1$ . This implies $a_{r}+b_{r}+c_{r}+d_{r}\leq 4k$ , and, in particular, that $p$ and $q$ together are contained in at least 3 red planes. Now consider the blue planes and note that $a_{b}+b_{b}+c_{b}+d_{b}\leq 4k$ — this is clear if each of sets $B^{\pm}_{p}\cap B^{\pm}_{q}$ contains at most $k$ blue planes, otherwise it follows by the same argument as above. Hence, $p$ and $q$ together are contained in $4k+3-(a_{b}+b_{b}+c_{b}+d_{b})\geq 3$ blue planes.

By Observation 4(2), $p$ and $q$ are contained in at most $6$ planes of $R^{*}\cup B^{*}$ . Combined with the argument above, this implies $p$ and $q$ together are contained in exactly 3 planes of each color. It follows that $a_{r}+b_{r}+c_{r}+d_{r}=a_{b}+b_{b}+c_{b}+d_{b}=4k$ , which, by the assumption $a_{r}=k+1$ , implies $b_{r}=c_{r}=k$ and $d_{r}=k-1$ . Since $|R^{-}_{p}|=2k+1$ and $b_{r}+d_{r}=2k-1$ , there are exactly 2 red planes containing $q$ below $p$ . Similarly, since $|R^{-}_{q}|=2k+1$ and $b_{r}+d_{r}=2k-1$ , there are exactly 2 red planes containing $p$ below $q$ . But then $p$ and $q$ are contained in a total of $4$ red planes, a contradiction.

This exhausts all possibilities and, hence, $|R_{p}^{\pm}\cap R_{q}^{\pm}|,|B_{p}^{\pm}\cap B_{q}^{\pm}|\leq k$ for all combinations of signs, completing the proof.

To summarize, once we construct $L$ in time $O^{*}(n+m)$ , to compute an eight-partition, it is sufficient, by Claim 2, to find two vertices $p,q\in L$ satisfying $X(p,q)=Y(p,q)=0$ . In particular, it is possible to construct an eight-partition by enumerating all the $\Theta(m^{2})$ pairs of vertices in $L$ ; the exact running time depends on how efficiently one can check candidate pairs. Below, we describe how to reduce the amount of remaining work to $O((m+n)\log m)$ .

Speed up

For simplicity of later calculations, we orient $L$ in the $y$ -direction (which is possible by Lemma 4.3) and view it as an alternating sequence of edges and vertices, starting and ending with a half-line. We denote these elements by $x_{1},x_{2},\dotsc,x_{m}$ . Recall that the goal is to identify $i,j\in[m]$ so that $x_{i},x_{j}$ are vertices and $X(x_{i},x_{j})=Y(x_{i},x_{j})=0$ .

We extend the definition of $X,Y$ as follows. If $x_{i},x_{j}$ are both edges, we pick arbitrary points $p$ and $q$ in the open edges $x_{i}$ and $x_{j}$ , respectively, and set $X(x_{i},x_{j})\coloneq X(p,q)$ and $Y(x_{i},x_{j})\coloneq Y(p,q)$ ; the cases where $x_{i}$ is an edge or $x_{j}$ is an edge, but not both, are handled analogously. Note that specifying the (open) edges containing $p$ and $q$ is sufficient to determine $X$ and $Y$ , hence the definition is unambiguous. Define $\pi\colon[m]^{2}\to\mathbb{Z}^{2}$ by

\pi(i,j)\coloneq(X(x_{i},x_{j}),Y(x_{i},x_{j})).

With this setup, our goal is to identify a point $(i,j)\in[m]^{2}$ (corresponding to a pair of vertices on $L$ ) such that $\pi(i,j)=\mathbf{0}$ .

We define a grid curve $C$ to be a sequence of points $(i_{1},j_{1}),\dots,(i_{t},j_{t})$ in $\mathbb{Z}^{2}$ such that $(i_{\ell+1},j_{\ell+1})\in\{(i_{\ell},j_{\ell}),(i_{\ell\pm 1},j_{\ell})(i_{\ell},j_{\ell\pm 1})\}$ for each $\ell\in[t-1]$ . In words, a grid curve is a walk in $\mathbb{Z}^{2}$ which, at each step, does not move at all or moves by exactly one unit up/down/left/right. A curve is closed if $(i_{1},j_{1})=(i_{t},j_{t})$ . A grid curve is simple if non-consecutive points are distinct (we think of the start and end points as consecutive) — so the curve does not revisit a point after it moves away from the point.

To each grid curve $C$ , we associate a piecewise linear curve $\overline{C}$ in $\mathbb{R}^{2}$ , consisting of line segments connecting consecutive points $(i_{\ell},j_{\ell}),(i_{\ell+1},j_{\ell+1})$ of $C$ for each $\ell\in[t-1]$ . For a curve $\overline{C}$ not passing through the origin $\mathbf{0}$ , the winding number $w(\overline{C})$ about $\mathbf{0}$ is defined in the standard way. Slightly abusing notation, we set $w(C):=w(\overline{C})$ . In particular, provided $\overline{C}$ misses the origin,

w(C)=w(\overline{C})=\begin{cases*}0&if $\overline{C}$ does not wind around $\mathbf{0}$,\\ n>0&if $\overline{C}$ winds around $\mathbf{0}$ $n$ times counterclockwise,\\ n<0&if $\overline{C}$ winds around $\mathbf{0}$ $-n$ times clockwise.\end{cases*}

We omit the rigorous definition of $w(C)$ as a contour integral in the complex plane since it does not add to the discussion and, instead, refer the reader to [15, Chapter 4.4.4].

Our algorithm proceeds as follows:

[Step 1]
1.

Set $C\coloneq T$ (see Definition 4.8). If $\pi(C)$ meets $\mathbf{0}$ , then stop — we have found a point that maps to $\mathbf{0}$ (see Lemma 4.11). Otherwise $\pi(\overline{C})$ has odd winding number, by Lemma 4.12.
2.

Construct two simple closed curves $C_{1}$ , $C_{2}$ so that (a) $\overline{C}=\overline{C}_{1}+\overline{C}_{2}$ , (b) at least one of $\pi(C_{1}),\pi(C_{2})$ has odd winding number (unless they meet $\mathbf{0}$ ), (c) the regions enclosed by $\overline{C}_{1}$ and $\overline{C}_{2}$ partition the region enclosed by $\overline{C}$ , and (d) the area enclosed by each of $\overline{C}_{1},\overline{C}_{2}$ is a fraction of that enclosed by $\overline{C}$ (see Lemma 4.16).
3.

If $\pi(C_{1})$ or $\pi(C_{2})$ meets $\mathbf{0}$ , then stop — we found a point that maps to $\mathbf{0}$ , by Lemma 4.11.
4.

Compute $w(\pi(C_{1}))$ and $w(\pi(C_{2}))$ , and replace $C$ with the one with the odd winding number. Goto Step 2.

We now proceed to fill in the details, starting with the definition of the initial curve $T$ .

Definition 4.8 (The triangular grid curve $T$ ).

The simple closed grid curve $T$ traverses a triangular path defined as follows:

•

Starting with the bottom horizontal side of the grid $[m]^{2}$ , $T$ traverses the points

$(x_{1},x_{1}),(x_{2},x_{1}),\dots,(x_{m},x_{1}),$
•

continuing along the right vertical side of the grid $[m]^{2}$ along the points

$(x_{m},x_{1}),(x_{m},x_{2}),\dots,(x_{m},x_{m}),$
•

finally, traversing back diagonally along

$(x_{m},x_{m}),(x_{m-1},x_{m}),(x_{m-1},x_{m-1}),(x_{m-2},x_{m-1}),\dots,(x_{1},x_{2}),(x_{1},x_{1}).$

Along the diagonal side of $T$ , we are really only interested in points of the form $(x_{\ell},x_{\ell})$ with $\ell\in[m]$ . However, since this doesn’t give a grid curve, we “patch” it up by introducing intermediate points. Fortunately, this does not change the desired properties of $T$ .

Lemma 4.9.

If $C$ is a grid curve, then $\pi(C)$ is a grid curve. Moreover, if $L$ has already been computed, $\pi(C)$ can be computed in time $O(n+|C|)$ .

Proof 4.10.

Consider a step in $C$ from $(x_{i},x_{j})$ to $(x_{i+1},x_{j})$ , where $x_{i}$ is an edge of $L$ and $x_{i+1}$ is a vertex. Then $x_{i+1}$ is contained in the planes that contain $x_{i}$ and one additional plane $H$ . Suppose, without loss of generality, that $H$ is red. This means that the cardinality of one of the sets $R_{p}^{\pm}$ changes by one. Hence, the cardinality of $R_{p}^{\pm}\cap R_{q}^{\pm}$ , for each combination of signs, changes by at most one — if $H$ contains $q$ , nothing changes. It follows that the function $X$ changes by at most one, and the function $Y$ remains unchanged.

Note that, up to symmetry, only one such transition or its reverse occurs in a single step of $C$ . We’ve shown that each step causes either $X$ or $Y$ (but not both) to change by at most one, and, hence, $\pi(C)$ is a grid curve.

The computation can be carried out in constant time per incident edge-vertex pair of $C$ , since $L$ has been already computed, after a $O(n)$ -time initialization that computes $X,Y$ at an arbitrary starting point of $C$ by brute force.

Lemma 4.9 immediately implies the following.

Lemma 4.11.

If $\overline{\pi(C)}$ meets $\mathbf{0}$ , then some point of $C$ is mapped to $\mathbf{0}$ .

A key property of the triangular grid curve $T$ is the following.

Lemma 4.12.

If $\mathbf{0}\not\in\pi(T)$ , then $w(T)$ is odd.

Proof 4.13.

Let $N\coloneqq 4k+2$ , and let $H,V,D$ be the images (under $\pi$ ) of the horizontal, vertical, diagonal sides of $T$ , respectively. Note that $\pi(T)$ is the concatenation of $H,V,$ and $D$ in that order.

Observe that if $p=q=x_{i}$ with $i\in[m]$ , then $|R_{p}^{+}\cap R_{q}^{-}|=|R_{p}^{-}\cap R_{q}^{+}|=0$ . Hence, $X(x_{i},x_{i})\in\{4k+1,4k+2\}$ depending on whether $x_{i}$ is contained in one or two red planes. Similarly, $Y(x_{i},x_{i})\in\{4k+1,4k+2\}$ . Hence $\pi(x_{i},x_{i})\in\{(N,N),(N-1,N-1)\}$ and, in particular, $\pi(x_{i},x_{i})=(N,N)$ if $x_{i}$ is an edge. Along with Lemma 4.9, this implies that the grid curve $D$ is a closed walk on the points in $\{N-2,N-1,N,N+1\}^{2}\setminus\{\mathbf{0}\}$ starting and ending at the point $(N,N)$ .

Noting that $x_{1}$ and $x_{m}$ are half-lines contained in the same red plane, and that every red plane that lies above $x_{1}$ lies below $x_{m}$ and vice versa, we obtain $\pi(x_{m},x_{1})=(-N,-N)$ . Hence, $H$ is a grid curve from the point $(N,N)$ to $(-N,-N)$ and $V$ is a grid curve from the point $(-N,-N)$ to $(N,N)$ .

The discussion above implies that $w(T)$ is equal to the winding number of the concatenation of $V$ and $H$ . We argue below that $V$ is the image of $H$ under a rotation by 180° around the origin, i.e., the map $(x,y)\mapsto(-x,-y)$ . Since, by assumption, neither $H$ nor $V$ contain $\mathbf{0}$ , the concatenation of $H$ and $V$ has odd winding number as claimed.

Specifically, we need to show that $\pi(x_{i},x_{1})=-\pi(x_{m},x_{i})$ . Since $\pi$ is symmetric in the two arguments, it suffices to show that $\pi(x_{1},x_{i})=-\pi(x_{m},x_{i})$ . As mentioned before, every plane that lies above $x_{1}$ lies below $x_{m}$ and vice versa. That is, $R_{x_{1}}^{+}=R_{x_{m}}^{-}$ and $R_{x_{1}}^{-}=R_{x_{m}}^{+}$ , and similarly $B_{x_{1}}^{+}=B_{x_{m}}^{-}$ and $B_{x_{1}}^{-}=B_{x_{m}}^{+}$ . The claim is now obvious from the definition of the functions $X$ and $Y$ .

Lemma 4.14.

If $w(\pi(C))$ is odd, then there is a point $(i,j)\in\mathbb{Z}^{2}$ enclosed by $\overline{C}$ with $\pi(i,j)=\mathbf{0}$ .

Proof 4.15.

A grid square $S$ is a simple closed grid curve of the form

(i,j),(i+1,j),(i+1,j+1),(i,{j+1}),({i},{j})

with $(i,j)\in\mathbb{Z}^{2}$ . A square is $\overline{S}$ for some grid square $S$ . If there is a grid square $S$ enclosed by $\overline{C}$ such that $\pi(S)$ meets $\mathbf{0}$ , then we are done by Lemma 4.11. Otherwise, note that $\overline{\pi(C)}$ is the sum of the images of the corresponding squares. Hence, there is a grid square $S$ with $w(\pi(S))$ odd. By Lemma 4.9, $\pi(S)$ is a grid curve. By enumerating all possibilities (see Fig. 2), we conclude that $w(\pi(S))$ cannot be odd.

Next, we show how to decompose a curve $C$ . We restrict our attention to “trapezoidal” curves: Such a curve is the boundary of the intersection of the region bounded by the initial triangle $T$ with a grid-aligned rectangle. This property is maintained inductively.

Lemma 4.16.

Given a trapezoidal curve $C$ whose image misses $\mathbf{0}$ , with $w(\pi(C))$ odd, we can construct two trapezoidal curves $C_{1}$ and $C_{2}$ so that

[(i)]
1.

the region $R$ surrounded by $\overline{C}$ is partitioned into region $R_{1}$ surrounded by $\overline{C}_{1}$ and region $R_{2}$ surrounded by $\overline{C}_{2}$ .
2.

$\operatorname{area}(R_{1}),\operatorname{area}(R_{2})\leq c\cdot\operatorname{area}(R)$ , for an absolute constant $c<1$ .
3.

either $\mathbf{0}$ is in the image of $C_{1}$ and $C_{2}$ or $w(\pi(C))=w(\pi(C_{1}))+w(\pi(C_{2}))$ .

Proof 4.17.

We already noted that the image of a grid square cannot have odd winding number, therefore $R$ is not a grid square. As long as $R$ is at least two units high, divide it by a horizontal grid chord into two near-equal-height pieces (that is, the two parts have equal height, or the lower one is one smaller) producing two regions $R_{1}$ and $R_{2}$ . The curves $C_{1}$ and $C_{2}$ are the boundaries of the regions (refer to Fig. 3). If the height of $R$ is one, perform a similar partition by a vertical chord into to near-equal-width pieces.

Property (1) is satisfied by construction. If the image of the new chord misses $\mathbf{0}$ , then both $C_{1}$ and $C_{2}$ avoid $\mathbf{0}$ and property (3) follows from the properties of the winding number on the plane. Finally, an easy calculation shows that, if the split height/width is even, then each part contains at most $3/4$ of the original area; this fraction can rise to $5/6$ if $R$ has odd width or length (the extreme case is achieved at width/length of three), which proves property (2).

Lemma 4.18.

Given a simple closed grid curve $C$ in $[m]^{2}$ we can determine whether $\pi(C)$ contains a zero. If not, we can compute $w(\pi(C))$ , all in time $O(|C|+n)$ .

Proof 4.19.

By Lemma 4.9, we can trace $\pi(C)$ step by step and, in particular, detect whether $\mathbf{0}\in\pi(C)$ . So suppose this is not the case.

Consider the (open) ray $\rho$ from the origin directed to the right in $\mathbb{Z}^{2}$ . To determine the winding number of the curve $\overline{\pi(C)}$ not passing through the origin, it’s sufficient to count how many times the curve crosses the ray $\rho$ . We can compute the number of times $\overline{\pi(C)}$ crosses $\rho$ by computing $\pi$ for every vertex of $C$ in order and counting the number of times $(X,0)$ occurs along it, with $X>0$ .

As $\overline{\pi(C)}$ may partially overlap $\rho$ , we need to check whether $\overline{\pi(C)}$ arrives at $(X,0)$ with $X>0$ from below the $X$ -axis and (possibly after staying on the axis for a while) departs into the region above $X$ -axis, or vice versa. That would count as a signed crossing. Arriving from below and returning below, or arriving from above and returning above, does not count as a crossing.

All of the above calculations can be done in time O(1) per step of $\pi(C)$ , after proper initialization, by Lemma 4.9.

Running time

We now analyze the running time of the algorithm we described. We can traverse a length- $O(m)$ closed grid curve $C$ , compute its image $\pi(C)$ , and check whether it passes through the origin in time $O(m+n)$ by Lemma 4.9. One can check whether $\pi(C)$ winds around the origin an odd number of times by Lemma 4.18, also in time $O(m+n)$ .

The number of rounds of the main loop of the algorithm is $O(\log m)$ , as the starting curve cannot enclose an area larger than $O(m^{2})$ and areas shrink by a constant factor in every iteration, by Lemma 4.16. Combining everything together, we conclude that $L$ can be computed in $O^{*}(n+m)$ time, and the algorithm can then identify the pair of vertices of $L$ corresponding to an eight-partition in at most $O(\log m)$ rounds, each costing at most $O(m+n)$ . This concludes the proof of Theorem 4.2.

References

[1] Pankaj K. Agarwal and Jirí Matousek. Dynamic half-space range reporting and its applications. Algorithmica, 13(4):325–345, 1995.
[2] Artur Andrzejak, Boris Aronov, Sariel Har-Peled, Raimund Seidel, and Emo Welzl. Results on $k$ -sets and $j$ -facets via continuous motion. In Proceedings of the 14th Annual Symposium on Computational Geometry, pages 192–199, 1998.
[3] Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. Eight-Partitioning Points in 3D, and Efficiently Too. In 40th International Symposium on Computational Geometry (SoCG 2024), pages 8:1–8:15, 2024.
[4] David Avis. Non-partitionable point sets. Information Processing Letters, 19(3):125–129, 1984.
[5] Pavle Blagojević, Florian Frick, Albert Haase, and Günter Ziegler. Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem. Transactions of the American Mathematical Society, 370(10):6795–6824, 2018.
[6] Pavle V. M. Blagojević and Roman Karasev. Partitioning a measure in $\mathbb{R}^{3}$ . Manuscript, 2016.
[7] Timothy M. Chan. A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM, 57(3):16:1–16:15, 2010.
[8] Jesús A. De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil H. Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, 56(3):415–511, 2019.
[9] Herbert Edelsbrunner. Edge-skeletons in arrangements with applications. Algorithmica, 1:93–109, 1986.
[10] Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer, 1987.
[11] Branko Grünbaum. Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific Journal of Mathematics, 10(4):1257–1261, 1960.
[12] H. Hadwiger. Simultane Vierteilung zweier Körper. Archiv der Mathematik (Basel), 17:274–278, 1966.
[13] Sariel Har-Peled. Geometric Approximation Algorithms. American Mathematical Society, USA, 2011.
[14] Christian Knauer, Hans Raj Tiwary, and Daniel Werner. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. In STACS’11, pages 649–660, 2011.
[15] Steven George Krantz. Handbook of Complex Variables. Springer, 1999.
[16] Chi-Yuan Lo, Jiří Matoušek, and William Steiger. Algorithms for ham-sandwich cuts. Discrete & Computational Geometry, 11(4):433–452, 1994.
[17] Jiří Matoušek. Using the Borsuk–Ulam Theorem. Springer Berlin Heidelberg, 2003.
[18] Nimrod Megiddo. Partitioning with two lines in the plane. Journal of Algorithms, 6(3):430–433, 1985.
[19] Edgardo Roldán-Pensado and Pablo Soberón. A survey of mass partitions. Bulletin of the American Mathematical Society, 2021.
[20] Micha Sharir, Shakhar Smorodinsky, and Gábor Tardos. An improved bound for k-sets in three dimensions. Discrete & Computational Geometry, 26(2):195–204, 2001.
[21] Géza Tóth. Point sets with many $k$ -sets. Discrete & Computational Geometry, 26(2):187–194, 2001.
[22] Rade T. Živaljević. Topological methods. In Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, pages 551–580. CRC Press LLC, 3rd edition, 1997.
[23] F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, and Mike Paterson. Partitioning space for range queries. SIAM Journal on Computing, 18(2):371–384, 1989.

Appendix A Limit arguments

We prove some standard facts using limit arguments.

Lemma A.1 (Limit argument for finite point sets).

Let $X\subseteq\left(\mathbb{S}^{3}\right)^{3}$ be a compact subset such that, for all $\mu$ mass distributions (with connected support) on $\mathbb{R}^{3}$ there is a plane configuration $\mathcal{H}\in X$ that eight-partitions $\mu$ ; then for any set $P$ of points in $\mathbb{R}^{3}$ , there is a configuration $\mathcal{H}_{\infty}\in X$ that eight-partitions the point set.

Proof A.2.

Let $n$ be the number of points in $P$ . Let $\mu_{i}$ be the measure defined as follows. At every point in $P$ , place a ball of radius $\varepsilon_{i}=\frac{1}{2^{i}}$ with uniform density and total mass $(1-\varepsilon_{i})/n$ ; finally, add a normal Gaussian distribution “on the background,” with total mass $\varepsilon_{i}/n$ . Note that the total measure $\mu_{i}$ of the complement of the union of balls is less than $\varepsilon_{i}$ .

By choosing $i$ large enough, we can assume that a plane can intersect a collection of balls only if their centres are coplanar; hence, without loss of generality, we can assume that this happens for $i=1$ .

By assumption, there is a plane configuration $\mathcal{H}_{i}$ that eight-partitions the mass $\mu_{i}$ for each $i$ ; by compactness of $X$ , there is a subsequence $\mathcal{H}_{i_{j}}$ that converges to some limit $\mathcal{H}_{\infty}$ ; up to reindexing we can assume that the original sequence $\mathcal{H}_{i}$ does. The obtained limit point eight-partitions the original point set $P$ : in fact, there is a $i_{0}$ big enough such that for every orthant $\alpha\in\mathbb{Z}_{2}^{3}$ and any $m\geq i_{0}$ , every point $p\in P\cap\mathcal{O}^{\mathcal{H}_{\infty}}_{\alpha}$ is “far away” (e.g., at least $1/{2^{i_{0}}}$ ) from the planes in the configuration $\mathcal{H}_{m}$ ; hence

\frac{1-\varepsilon_{m}}{n}\lvert P\cap\mathcal{O}^{\mathcal{H}_{\infty}}_{\alpha}\rvert\leq\mu_{m}(\mathcal{O}^{\mathcal{H}_{m}}_{\alpha})=\frac{1}{8}.

Taking the limit in $m$ we obtain the desired result.

Corollary A.3.

Let $X$ and $P$ as above. If $\mathcal{H}_{\infty}=(H_{1},H_{2},H_{3})$ is the configuration constructed in the proof of Lemma A.1, then any plane $H_{i}$ in $\mathcal{H}_{\infty}$ bisects $P$ and any pair $(H_{i},H_{j})$ four-partitions the points.

Proof A.4.

For simplicity we show the result for the first plane $H_{1}$ and the pair $(H_{1},H_{2})$ , all the other cases are identical. First, construct $\mu_{i}$ and $\mathcal{H}_{i}=(H_{i,1},H_{i,2},H_{i,3})$ converging to the limit $\mathcal{H}_{\infty}$ as in the proof of Lemma A.1.

Again, by choosing $i_{0}$ big enough we obtain that, for any $m\geq i_{0}$ and any sign $\alpha\in\mathbb{Z}_{2}$ every point $p\in P\cap H_{1}^{\alpha}$ is sufficiently far form $H_{m,1}$ hence

\frac{1-\varepsilon_{m}}{n}\lvert P\cap H_{1}^{\alpha}\rvert\leq\mu_{m}(H_{m,1}^{\alpha})=\frac{1}{2}.

Similarly, for any pair of signs $(\alpha_{1},\alpha_{2})\in\mathbb{Z}_{2}^{2}$ , any point $p\in P\cap H_{1}^{\alpha_{1}}\cap H_{2}^{\alpha_{2}}$ is sufficiently far from both $H_{m,1}$ and $H_{m,2}$ , therefore

\frac{1-\varepsilon_{m}}{n}\lvert P\cap H_{1}^{\alpha_{1}}\cap H_{2}^{\alpha_{2}}\rvert\leq\mu_{m}(H_{m,1}^{\alpha_{1}}\cap H_{m,2}^{\alpha_{2}})=\frac{1}{4}.

By taking the limit we obtain the desired result.

Lemma A.5 (Limit argument for mass distributions with possibly disconnected support).

Let $X$ be a compact set in $\left(\mathbb{S}^{3}\right)^{3}$ such that, for any mass distribution with connected support there is a configuration $\mathcal{H}\in X$ that eight-partitions the measure. Let $\mu$ be a “general” mass distribution. Then there is a plane arrangement $\mathcal{H}_{\infty}\in X$ that eight-partitions $\mu$ .

Proof A.6.

Define $\varepsilon_{i}\coloneq\frac{1}{2^{i}}$ and let $\mu_{i}$ the measure defined, on a measurable set $A\subseteq\mathbb{R}^{3}$ , as

\mu_{i}(A)\coloneqq\left(1-\varepsilon_{i}\right)\mu(A)+\varepsilon_{i}\mathcal{N}(A),

where $\mathcal{N}$ is a normal Gaussian distribution on $\mathbb{R}^{3}$ . Then, $\mu_{i}$ is a mass distribution with connected support hence there is a configuration $\mathcal{H}_{i}$ that eight-partitions $\mu_{i}$ . By compactness, up to taking a subsequence, $\mathcal{H}_{i}$ converges to a configuration $\mathcal{H}_{\infty}$ .

Now, for any $\alpha\in\mathbb{Z}_{2}^{3}$ , we have that

\left(1-\varepsilon_{i}\right)\mu(\mathcal{O}^{\mathcal{H}_{i}}_{\alpha})\leq\mu_{i}(\mathcal{O}^{\mathcal{H}_{i}}_{\alpha})=\frac{1}{8}.

For any fixed measure $\tilde{\mu}$ , the map $\mathcal{H}\to\tilde{\mu}(\mathcal{O}^{\mathcal{H}}_{\alpha})$ is continuous; hence by taking the limit in $i$ we obtain that, for all $\alpha\in\mathbb{Z}_{2}^{3}$ ,

\mu(\mathcal{O}^{\mathcal{H}_{\infty}}_{\alpha})\leq\frac{1}{8}.

However, since

\sum_{\alpha\in\mathbb{Z}_{2}^{3}}\mu(\mathcal{O}^{\mathcal{H}_{\infty}}_{\alpha})=\mu(\mathbb{R}^{3})=1,

it follows that all the previous inequalities are equalities.

Appendix B Topological Lemmas

In this section, we provide proofs for the classical homotopical results used in the proof of Theorem 2.2.

Proposition B.1.

If $A\in O(d)$ is an orthogonal matrix, then the induced continuous map $A\colon\mathbb{S}^{d-1}\rightarrow\mathbb{S}^{d-1}$ has degree $\deg(A)=\det(A)$ .

Proof B.2.

Assume $\det(A)=1$ (i.e., $A\in SO(d)$ ).

Let $P$ an invertible matrix that puts $A$ in Jordan normal form, where $R_{\theta}$ denotes the $2\times 2$ matrix of the rotation by $\theta$ :

A=P^{-1}\begin{pmatrix}R_{\theta_{1}}&&&&\\ &R_{\theta_{2}}&&&\\ &&\ddots&&\\ &&&R_{\theta_{k}}&\\ &&&&\textnormal{Id}_{d-2k}\end{pmatrix}P.

Then, there is a path $\gamma$ from the $d\times d$ identity matrix $\textnormal{Id}_{d}$ to the matrix $A$ defined as:

\gamma(t)=P^{-1}\begin{pmatrix}R_{t\theta_{1}}&&&&\\ &R_{t\theta_{2}}&&&\\ &&\ddots&&\\ &&&R_{t\theta_{k}}&\\ &&&&\textnormal{Id}_{d-2k}\end{pmatrix}P,

with $\gamma(0)=\textnormal{Id}_{d}$ and $\gamma(1)=A$ . As a result, the map $A\colon\mathbb{S}^{d-1}\rightarrow\mathbb{S}^{d-1}$ is homotopic to the identity through the homotopy $H\colon\mathbb{S}^{d-1}\times\left[0,1\right]\rightarrow\mathbb{S}^{d-1}$ ; $H(x,t)=(\gamma(1-t))x$ . Hence $\deg(A)=\deg(\textnormal{Id}_{d})=1$ .

Suppose now $\det(A)=-1$ , then $QA\in SO(d)$ where

Q\coloneqq\begin{pmatrix}\textnormal{Id}_{d-1}&\\ &-1\end{pmatrix}.

This means that $1=\deg(QA)=\deg(Q)\deg(A)=-\deg(A)$ .

Proposition B.3.

Let $f\colon\mathbb{S}^{n-1}\rightarrow\mathbb{S}^{n-1}$ be a continuous antipodal map. Then $\deg(f)\neq 0$ .

Proof B.4.

For a contradiction, suppose there exists a continuous antipodal function $f\colon\mathbb{S}^{n-1}\rightarrow\mathbb{S}^{n-1}$ of degree zero.

Then $f$ can be extended to a map $F\colon D^{n}\rightarrow\mathbb{S}^{n-1}$ ; using this map it is possible to construct $\tilde{F}\colon\mathbb{S}^{n}\rightarrow\mathbb{S}^{n-1}$ :

\tilde{F}(x_{1},\dots,x_{n+1})=\begin{cases}F(x_{1},\dots,x_{n})&\mbox{if }x_{n+1}\geq 0,\\ -F(-x_{1},\dots,-x_{n})&\mbox{if }x_{n+1}\leq 0.\end{cases}

$\tilde{F}$ is well defined because on the intersection of the two patches (i.e., the horizontal equator) both sides coincide with $f$ . $\tilde{F}$ is also antipodal: when $x_{n+1}\geq 0$

\tilde{F}(-(x,x_{n+1}))=-F(-(-x))=-F(x)=-\tilde{F}((x,x_{n+1})),

while for $x_{n+1}\leq 0$ ,

\tilde{F}(-(x,x_{n+1}))=F(-x)=-(-F(-x))=-\tilde{F}((x,x_{n+1})).

Thus $\tilde{F}$ violates Borsuk-Ulam theorem.

Appendix C Four-partitioning in the plane with a prescribed bisector

This section is devoted to the proof of Lemma 2.2. We require the following standard fact.

Lemma C.1.

Given a mass distribution on $\mathbb{R}^{d}$ and a direction $v\in\mathbb{S}^{d-1}$ , there is a unique hyperplane normal to $v$ bisecting the mass.

Proof C.2.

Let $H_{v}(a)$ be the hyperplane $\{x\in\mathbb{R}^{d}:x\cdot v=a\}$ , and set $H^{+}_{v}(a):=\{x\in\mathbb{R}^{d}:x\cdot v>a\}$ to be the positive half-space determined by $H_{v}(a)$ . The family of planes with $v$ as normal is ${\{x\cdot v=a:a\in\mathbb{R}\}}$ . Since the hyperplane $H^{+}_{v}(a)$ varies continuously with $a$ , $\lim_{a\to-\infty}\mu(H^{+}_{v}(a))=0$ , and $\lim_{a\to\infty}\mu(H^{+}_{v}(a))=1$ , the intermediate value theorem implies the existence of a bisecting hyperplane.

To prove uniqueness, first observe that, if $\mu(H^{+}_{v}(a))=1$ then for any $b\geq a$ , $\mu(H^{+}_{v}(b))=1$ and analogously if $\mu(H^{+}_{v}(a))=0$ then for any $b\leq a$ , $\mu(H^{+}_{v}(b))=0$ . Denote by $\bar{a}$ the maximum value $a$ for which $\mu(H^{+}_{v}(a))=0$ ( $-\infty$ if there is none), similarly define $\bar{b}$ as the minimum value $b$ for which $\mu(H^{+}_{v}(b))=1$ ( $\infty$ if there is none).

Since the support is connected, the function $a\mapsto\mu(H^{+}_{v}(a))$ is strictly increasing in the interval $[\bar{a},\bar{b}]$ and identically $0$ or $1$ outside of it; therefore there is a unique value $x\in[\bar{a},\bar{b}]$ for which $\mu(H^{+}_{v}(x))=\frac{1}{2}$ .

For convenience, we restate the lemma here. Both the lemma and proof are due to [6]. \blagkarasev*

Proof C.3.

Suppose, without loss of generality, that $v=(0,1)$ . We first prove existence. Let $\alpha\in[0,\pi/2]$ , and rotate $v$ counterclockwise and clockwise by angle $\alpha$ to obtain $u_{\alpha}$ and $w_{\alpha}$ , respectively. Then, by Lemma C.1 there exist unique lines $\ell_{\alpha}$ and $m_{\alpha}$ that are perpendicular to $u_{\alpha}$ and $w_{\alpha}$ , respectively, and bisect $\mu$ . Note that $v$ bisects the angle between $\ell_{\alpha}$ and $m_{\alpha}$ .

The (oriented) lines $\ell_{\alpha}$ and $m_{\alpha}$ partition the plane into four octants, which we label $P_{N},P_{E},P_{S},P_{W}$ (north, east, south, west) in the obvious manner. Since both lines are bisecting, we have

\mu(P_{N})=\mu(P_{S})=x,\quad\mu(P_{W})=\mu(P_{E})=\mu(\mathbb{R}^{2})/2-x=y.

When $\alpha$ tends to 0, $P_{W}$ and $P_{E}$ tend to empty sets and evidently $x>y$ for $\alpha$ sufficiently close to $0$ . When $\alpha$ tends to $\pi/2$ , $P_{N}$ and $P_{S}$ tend to empty sets and then $x<y$ for $\alpha$ sufficiently close to $\pi/2$ . Since $x$ depends continuously on $\alpha$ , we must have $x=y$ somewhere in between, by the intermediate value theorem. Thus, we have existence.

We now show uniqueness. Assume we have a partition $P_{N},P_{E},P_{S},P_{W}$ with angle $\alpha$ and another partition $Q_{N},Q_{E},Q_{S},Q_{W}$ with angle $\alpha^{\prime}$ . Assume without loss of generality that $\alpha^{\prime}\leq\alpha$ . Moreover, since for $\alpha^{\prime}=\alpha$ the partition is defined uniquely, we may assume $\alpha^{\prime}<\alpha$ . Let $p=\ell_{\alpha}\cap m_{\alpha}$ and consider the following cases:

1.

$p\in Q_{N}$ : In this case $P_{N}\subset Q_{N}$ and both sets have the same measure. This contradicts connectivity of the set where the density is positive, since the density is positive in $Q_{S}$ and in $P_{N}$ , it must be positive somewhere in $Q_{N}\setminus P_{N}$ , implying $\mu(Q_{N})>\mu(P_{N})$ .
2.

$p\in Q_{E}$ : In this case $P_{W}\subset Q_{W}$ and we obtain a similar contradiction.
3.

$p\in Q_{S}$ and $p\in Q_{W}$ are similar to considered cases.

Since the lines $\ell_{\alpha},m_{\alpha},\ell_{\alpha^{\prime}}$ , and $m_{\alpha^{\prime}}$ are distinct, this covers all cases. In each case, we obtain a contradiction, hence, we have uniqueness.

As for continuity, it follows from the standard fact that a map with compact codomain and closed graph must in fact be continuous. The codomain is compact since we are only interested in directions of the halving lines that afterwards produce halving lines continuously, thus working with $\mathbb{S}^{1}\times\mathbb{S}^{1}$ as the space of parameters.