Problem Statement
Consider a compact convex polytope $\mathcal{X} \subset \mathbb{R}^N$ and $n$ halfspaces defined by \begin{equation*} h_i = \{ x \in \mathbb{R}^N \mid a_i x \leq b_i \} \end{equation*} where $a_i^T \in \mathbb{R}^N$ and $b_i \in \mathbb{R}$.
I would like to find the set of $m$ (convex) partitions $\mathcal{P}_j = \{x \in \mathcal{X} \mid C_j x \leq d_j\}$ defined by these halfspaces.
Example
An example with $N=2$ is shown below:
In this example we have $n=3$ halfspaces and $m=6$ partitions.
What I've Tried
I know that the partitions can be created by considering all possible combinations of all the halfspaces and their negations, i.e., \begin{equation*} \mathcal{P}_1 = \left\{ x \in \mathcal{X} \mid \begin{bmatrix} a_1 x \leq b_1 \\ a_2 x \leq b_2 \\ \vdots \\ a_n x \leq b_n \end{bmatrix} \right\},~ \mathcal{P}_2 = \left\{ x \in \mathcal{X} \mid \begin{bmatrix} a_1 x > b_1 \\ a_2 x \leq b_2 \\ \vdots \\ a_n x \leq b_n \end{bmatrix} \right\},~ \mathcal{P}_3 = \left\{ x \in \mathcal{X} \mid \begin{bmatrix} a_1 x \leq b_1 \\ a_2 x > b_2 \\ \vdots \\ a_n x \leq b_n \end{bmatrix} \right\}, \dots \end{equation*}
However, this would require constructing $2^n$ partitions, and many of those will be empty. For example, in the $N=2$ case there are at most only $m = \frac{n(n+1)}{2}+1$ partitions.
Are there more efficient methods for constructing the partitions? In particular, I'm looking for an algorithm that generates the matrices $C_j$ and vectors $d_j$.
Possibly Related
- This question which considers the $N=2$ case
- The problem seems similar to constructing a Voronoi diagram, but we are given the edges of each partition rather than points inside them.
- Hyperplane Arrangements
Let's say the halfspaces/planes defining the original convex polytope are $\mathfrak{p}_1$ through $\mathfrak{p}_k$, and the splitting planes are $\mathfrak{p}_{k+1}$ through $\mathfrak{p}_{k+n}$.
(Each plane $\mathfrak{p}_i$ is defined by a $N$-dimensional real vector $\mathbf{y}_i$, $\mathbf{y}_i \in \mathbb{R}^N$, and a real scalar $d_i$, $d_i \in \mathbb{R}$, where point $\mathbf{x}$ is on the plane if and only if $\mathbf{x} \cdot \mathbf{y}_i = d_i$. Using OP's definition, if $\mathbf{x} \cdot \mathbf{y}_i - d_i \le 0$, $\mathbf{x}$ is inside the halfspace, outside otherwise. Essentially, if $\mathbf{v}_j$ are the vertices of a convex polytope, if there is a $\mathbf{v}_a$ and $\mathbf{v}_b$ such that $\mathbf{v}_a \cdot \mathbf{y}_i - d_i \lt 0$ and $\mathbf{v}_b \cdot \mathbf{y}_i - d_i \gt 0$, then plane $i$ does intersect the convex polytope. To detect polytope-plane intersection, one only needs to check the sign of the plane equation for each vertex, ignoring zeroes; and if there are vertices that yielded different signs, the plane does intersect the polytope, otherwise not.)
The vertices $\mathbf{v}_i \in \mathbf{R}^N$ of the polytope are at the intersections of each unique set of $N$ halfspaces/planes $\mathfrak{p}_i$. (That is, the intersection of $\mathfrak{p}_1, \mathfrak{p}_2, \dots, \mathfrak{p}_{N-1}, \mathfrak{p}_N$ defines $\mathbf{v}_1$; $\mathfrak{p}_1, \mathfrak{p}_2, \dots, \mathfrak{p}_{N-1}, \mathfrak{p}_{N+1}$ defines $\mathbf{v}_2$; and so on for all unique $N$-tuples. The polytope therefore has $k \choose N$ such vertices $\mathbf{v}_i$, i.e. $i = 1 \dots { k \choose N }$.)
Consider an algorithm that takes both the vertices and the planes defining a convex polytope, and a splitting plane, and produces either the two resulting polytopes (created by the plane splitting the polytope in two), or the original polytope (if the plane does not intersect with the polytope). (Note that because the polytope is convex, the splitting hyperplane either does not intersect, or intersects the polytope in up to two convex or degenerate parts. Degenerate parts have zero volume, so they can be discarded; degenerate parts do not generate a partitioned cell in this context.)
Start with a pool of exactly one convex polytope, the original one. Apply the algorithm to all polytopes in the pool for the first splitting plane (either keeping each polytope in the pool if the splitting plane does not split it into two non-degenerate convex polytopes, or replacing the polytope with the two non-degenerate convex polytopes in the pool); followed by applying the algorithm to all polytopes in the pool for the second splitting plane; and so on, for each splitting plane. At the end, the pool will contain exactly the convex polytopes corresponding to the partitions we are after.
Is this optimal? I don't know; I suspect it is not. There are obviously up to $2^n$ polytopes (partitions) generated this way. However, the test for checking whether a splitting plane affects a polytope is fast, if the vertices are kept within each polytope; essentially very efficiently in linear time wrt. number of vertices, with shortcut/early detection when the plane does split the polytope.
Similarly, if each vertex is labeled with the $N$ planes whose intersection it corresponds to, splitting the polytope by a plane becomes rather straightforward. First, the vertices are divided into three groups based on the sign of the plane equation (the third group corresponding to zero). If either the negative or the positive group is empty, the splitting plane does not split the polytope.
Edges split by the plane are the pairs of vertices in the positive and negative sets that share a plane label; this is trivial to calculate via linear interpolation. (You'll save a lot of calculation if you normalize the plane definitions so that the vector part has unit Euclidean norm.)
Calculate these new vertices for the current polytope, and add them to the zero set. One of the resulting polytopes has the vertices in the zero and the positive set; the other has the vertices in the zero and the negative set. To determine which planes are "still" included in each polytope (the splitting plane is included in both), check the original polytope planes against the vertices in each resulting polytope.
Algorithmically, this pretty much implements how a human doing the splitting operations on physical objects would do this. They would have an incoming tray, and an outgoing tray, and do the split operation on each incoming object, putting the results in the outgoing tray; and repeat this for each split operation. In this sense, it is pretty much a "brute force" approach; very unelegant.
In practice, especially as a computer program, I expect this to perform acceptably, noting that as $N$, $k$, and $n$ increase, the number of resulting partitions/polytopes/convex cells increases rather rapidly; there can be a lot of numerical data involved.