How would one construct conjunctively local predicate of order k for checking if a shape is Convex?
One way to construct $\Psi_{\mathrm {CONVEX }}$ is as follows: 
define $\phi_{i,j,k}(X) := \begin{cases} 1 &amp; \text{if $(x_i,x_j \in X \Rightarrow x_k\in X)$ } \\ 0 &amp; \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$.