1
$\begingroup$

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:

enter image description here

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

$\endgroup$
6
  • $\begingroup$ What are the rules for the generated cells? Equal volume? For Voronoi diagrams, each cell has exactly one point, with all points given as inputs. What are the knowns in your case? As stated, any partitioning works, so is the objective to find just one set (out of infinite number of solutions) of $n$ planes that split $\mathcal{X} \subset R^N$ into $m$ cells (non-degenerate polytopes)? $\endgroup$
    – Glärbo
    May 12, 2021 at 20:54
  • $\begingroup$ In particular, splitting each coordinate axis into $n_k$ ($k = 1 \dots N$) using axis-perpendicular planes at regular intervals yields $m = \sum_{k=1}^N n_k$ partitioning planes and $\prod_{k=1}^N n_k$ cuboid cells (hyperrectangles) (except for the ones near the surface of the original polytope, i.e. "surface" cells). It is not an optimal solution, but especially for $N \ge 3$ the number of cells grows very, very fast (compared to the number of partitioning planes). $\endgroup$
    – Glärbo
    May 12, 2021 at 20:59
  • $\begingroup$ The knowns are the hyperplanes/halfspaces $h_i$. The rules for the generated cells are that they (1) must be convex polytopes, (2) must be defined by the given hyperplanes, and (3) must be such that no hyperplanes "splits" a given cell. $\endgroup$ May 12, 2021 at 23:39
  • $\begingroup$ Since the halfspaces are given, using axis-perpendicular planes at regular intervals (i.e. constructing cuboid cells) doesn't solve the problem. The goal is not to find the partitioning planes, but rather to find a concise representation of each cell ($C_j$ and $d_j$) given the partitioning planes. Sorry if that wasn't clear in the original question. $\endgroup$ May 12, 2021 at 23:44
  • $\begingroup$ So, you basically have $2^k 3^n$ possible combinations of halfspaces (of $k$ halfspaces defining the polytope, and $n$ splitting planes or "two-sided" halfspaces), and you need a way to select/find the ones that are closed (polytopes) and not split by any splitting planes not part of the polytope boundary? (The $2^k$ term is because each of the polytope-defining halfspaces can either be selected or not selected; the $3^n$ is because each splitting plane can be used as-is, used reversed, or not used.) $\endgroup$
    – Glärbo
    May 12, 2021 at 23:54

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, this is exactly what I was looking for! I ended up checking whether a given hyperplane splits a polytope by solving a Linear Program rather than keeping track of all of the vertices. $\endgroup$ May 13, 2021 at 17:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .