How would one construct conjunctively local predicate of order k for checking if a shape is Convex?

Question

I was reading Minsky's and Papert's book on perceptrons and it had the definition of conjunctively local as follow (look at the last images if its still unclear):

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and: $$ \psi(X) = \begin{cases} 1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\ 0 \text{ otherwise. } \end{cases} $$

Then in the book they claim that testing if a figure $X$ drawn on a 2D Euclidean pixel plan $R$ is conjunctively local of order 3. First recall how one would text for convexity on $R$. Essentially one woul look at three points/pixels and draw a line segment joining the points and if the third chose point between them is not in the drawn figure $X$, then it would not be convex.

My question is given this knowledge, how does one show that $\Psi_{convex}(X)$ is conjuctively local of order 3? The order 3 seems sort of clear to me because each $\varphi$ only needs look at 3 points to test convexity. However, it remains unclear to me how one would construct a general $\Psi(X)$ such that it always test correctly for any drawn geometric shape if its convex or not. I guess maybe part of my quesiton is that the definition of conjuctively local is not clear to me. Is it correct to think of $\Psi$ as a function only on the given geometric shape or is it also a funciton fo the whole plane $R$? It seems clear how to construct $\Psi$ if we know the shape in advance but otherwise it doesn't seem we can fix one single architecture and be able to text for convexity.

---

Answer 1

One way to construct $\Psi_{\mathrm {CONVEX }}$ is as follows: define $\phi_{i,j,k}(X) := \begin{cases} 1 & \text{if $(x_i,x_j \in X \Rightarrow x_k\in X)$ } \\ 0 & \text{otherwise}\\\end{cases}$.

Now, we define the set $\Phi$ by picking all pairs of $x_i,x_j\in R$ and all $x_k$ that lie on the line segment between them, i.e. $\phi_{i,j,k}\in \Phi$ for all $x_i,x_j\in R$ and all $x_k\in \{x\in R\mid \exists\lambda\in [0,1]: x=\lambda x_i + (1-\lambda)x_j\}$.

Note that each $\phi_{i,j,k}$ depends on only three values of $R$ and that the shape $X$ is convex if and only if all $\phi_{i,j,k} \in \Phi$ have value $1$. So, according to your definition, $\Psi_{\mathrm {CONVEX }}$ is conjuctively local of order $3$.

This does not seem like a very practical approach to determine the convexity of a shape, in particular when $R = \mathbb{R}^2$, since that means $\Phi$ is of infinite size.

So the basic idea is that for given indices $i,j,k$, the $\phi_{i,j,k}$ are functions of $X$ and exactly three points of $R$: $x_i,x_j$ and $x_k$. The selection of their indices (i.e. the set $\Phi$) is independent of $X$, but does depend on $R$.