Given a 3D matrix of size $N \times N \times N$, let $\mathcal{S}$ be a set of points in the Matrix and $\mathcal{S}'$ be the complement of $\mathcal{S}$. Can we find a set of equations of the form:

$F: (f_1 \land f_2 \land \ldots \land fn)$

where $f_x$ is of the form

$f_x \implies ai + bj + ck + dN + e \text{ } \{<,>,=,\neq\} \text{ } 0$

$f_x$ is true if a point satisfies the aforementioned function and false otherwise

where $i,j,k$ are the indices of the grid points in the Matrix (which vary from 1 to $N$) and $a,b,c,d,e$ are integers such that

$F(\text{all points in }\mathcal{S}) = True$
$F(\text{all points in }\mathcal{S}') = False$

For example:
If $N = 4$, and $S = \{(1,1,1),(2,2,2),(3,3,3),(4,4,4)\}$, we can say that the functions $f_1 \implies i-k=0$ and $f_2 \implies j-k=0$ are one solution for this set.

Ideally we are interested in a solution with the minimum number of equations, but this is not necessary.


Yes. You can. You can use linear algebra and linear programming to find a $F$ that is true for all points in $S$ and false for all points in $S'$.

Small simplifications. Note that $d$ is unnecessary. $N$ is a constant, so without loss of generality we can assume $d=0$ (otherwise replace $e$ by $dN+e$). So, we will assume each $f$ has the form $ai+bj+ck+e \bowtie 0$. Also note that the contents of the matrix itself are irrelevant and all that matters is the set $S$. Finally, I will assume you are looking for integer values of $a,b,c,e$, with no limit on how large or small they are.

Finding a $f$. Let's start by showing how, given $S$, you can find a $f$ that is true for all points in $S$. There are several cases, according to which relational operator $f$ uses:

  • Equality: For $f$ of the form $ai+bj+ck+e=0$, consider the $a,b,c,e$ as four unknowns. For each point $(i,j,k) \in S$, we obtain a linear equation on these four unknowns. You can use linear algebra to find a value for $a,b,c,e$ such that $ai+bj+ck+e=0$ is true for all $(i,j,k) \in S$, if one exists: basically, you use Gaussian elimination to invert the matrix resulting from this system of equations. Moreover, you can find a basis for the set of all $a,b,c,e$ that are valid solutions.

    In this way, we either find zero, one, two, three, or four independent equality constraints $f$ that will be true for all points in $S$.

  • Less than or equal to: For $f$ of the form $ai+bj+ck+e \le 0$, we can use linear programming to find $a,b,c,e$ that make this inequality true for all $(i,j,k) \in S$. Each $(i,j,k) \in S$ yields a single linear inequality on the unknowns $a,b,c,e$. Form a system of inequalities obtained by all the points in $S$. Solving this then gives us a valid combination of values for $a,b,c,e$. There may be many solutions; linear programming will give you an arbitrary solution, not necessarily the best one.

    You can improve this to check whether there exists a single linear inequality that separates $S$ from $S'$: simply add the linear inequality $ai+bj+ck+e \ge 1$ for each $(i,j,k) \in S'$ to the system of linear equations above, and check whether it has a valid solution. If yes, then you have a single linear inequality $f$ that yields a minimal solution (an $F$ containing only a single $f$), and you are done. If not, next try the following heuristic to find a $f$ that separates $S$ from $S'$ as well as possible:

    Introduce unknowns $x_{i,j,k}$ for each $(i,j,k) \in S'$, and constrain them by $0 \le x_{i,j,k} \le 1$. Add constraints $ai+bj+ck+e \ge x_{i,j,k}$ for each $(i,j,k) \in S'$. Now use linear programming to search for values for $a,b,c,e$ that maximize the objective function $\sum_{(i,j,k) \in S'} x_{i,j,k}$. This will force $f$ to be true for all points in $S$ and aim to make it false for as many points in $S'$ as possible.

    If you want $a,b,c,e$ to be integers, use integer linear programming instead of linear programming.

  • Less than: For $f$ of the form $ai+bj+ck+e < 0$, we can adjust the above approach by using linear inequalities of the form $ai+bj+ck+e < 0$ (or $ai+bj+ck+e \le -1$ if we require $a,b,c,e$ to be integers) and carrying on as before.

  • Inequality: Simply swap the roles of $S$ and $S'$ and then use the approach for equalities.

Finding $F$. So, given sets $S,S'$, this shows how to find a single constraint $f$ that could be included in $F$. But how do we find a full $F$?

I don't know of any efficient way to find the optimal $F$. However, I can suggest a heuristic that I suspect will work well: use an iterative greedy algorithm, where at each iteration you find a $f$ that is true for all points in $S$ and that is false for as many points that haven't been covered yet as possible.

In particular, at each stage, we will have a candidate $F$ that is true for all points in $S$, and is false for some points in $S'$. Define $T = \{(i,j,k) \notin S : F(i,j,k)=\text{True}\}$. Our goal will be to find $f$ that is true for all points in $S$ and is false for as many points in $T$ as possible; then we will replace $F$ with $F \land f$.

Given $S,T$, how can we find $f$ that is true for all $S$ and false for as many points in $T$ as possible? Well, I've already described how. For each relational operator $\bowtie \in \{=,\ne,<,>\}$, use the procedures above to find a candidate $f$ that uses that operator and is true for all of $S$ and false for as much of $T$ as possible. This gives you four candidates for $f$. For each candidate, count how many elements of $T$ it is false for, and keep the best one you find.

In this way, I expect you'll fairly rapidly converge to a $F$ that is either optimal (contains the minimal number of clauses) or is close to optimal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.