is hyperplanar substructures realization in 2D. Consider the gadget given in Figure \[fig:nphardness\] from Section \[sec:hard2d\]. Suppose that each line is a plane seen from $xy$-plane in 3D. That is, each wireless node in Figure \[fig:nphardness\] has $z$-coordinate zero. In order to obtain a deployment in 3D, we just make a copy for each wireless node with the same $x$ and $y$-coordinates, and let their $z$-coordinates be equal to $1$.

From this point on, it is trivial to see that each wireless node is connected to its copy in 3D, and no other from the copies. Thus, the triangle flags become triangle prisms. And we can easily apply the proof given in Section \[fig:nphardness\].

Now that we have proved that proof given in Lemma \[lem:hard2d\] can be extended to 3D by Lemma \[lem:hard3d\], we can use the same method and extend the claim to higher dimensions.

\[thm:hardAllDimensions\] Hyperplanar substructures recognition is -hard in every dimension.

We already know that the problem is -hard in 2D by Lemma \[lem:hard2d\], and the hardness reduction can be extended to 3D by Lemma \[lem:hard3d\]. In this proof, we show that the very same reduction can be used to prove the claim for 4D, and 