How to find the normal of an n-dimensional hyperplane given n points on the plane?

Question

Given n many n-dimensional points how would one calculate the surface normal of the plane that they form? I'm hoping to implement this in python, so any tools that could help are also welcome.

Answer 1

Let us assume we have n dimensions and n points with coordinates $(x_{11},x_{12},...,x_{1n})$, $(x_{21},x_{22},...,x_{2n})$, ... , $(x_{n1},x_{n2},...,x_{nn})$. The most direct approach I see is to put them in the equation of the hyperplane and solve the following system of linear equations for $(a_1,a_2,...,a_n)$: $$\begin{cases} a_1x_{11}+a_2x_{12}+...+a_nx_{1n}=a_0 \\ a_1x_{21}+a_2x_{22}+...+a_nx_{2n}=a_0 \\ ...\\ a_1x_{n1}+a_2x_{n2}+...+a_nx_{nn}=a_0 \end{cases} $$ Then, the vector $(a_1,a_2,...,a_n)$ should be the normale of abovedefined hyperplane.

Answer 2

If we’re working in $\mathbb R^3$ and the three points are in general position so that they indeed define a unique plane, we can immediately write down an equation for it: $$\begin{vmatrix}x&y&z&1 \\ p_{1x}&p_{1y}&p_{1z}&1 \\ p_{2x}&p_{2y}&p_{2z}&1 \\ p_{3x}&p_{3y}&p_{3z}&1\end{vmatrix} = 0.$$ One way to understand this formula is that in homogeneous coordinates, the plane is the join of the three points—the set of all nontrivial linear combinations of them—so if you plug in the coordinates of any point on the plane into the first row of the above determinant, its rows will be linearly dependent.

If you formally substitute the standard basis vectors $\mathbf i$, $\mathbf j$ and $\mathbf k$ for $x$, $y$ and $z$, respectively, the above expression produces the cross product $(\mathbf p_2-\mathbf p_1)\times(\mathbf p_3-\mathbf p_1)$, which is an equivalent way to compute a normal to the plane.

This works in $\mathbb R^n$ as well: if the points $\mathbf p_1,\dots,\mathbf p_n$ define a unique hyperplane, then an equation for it is $$\begin{vmatrix}\mathbf x&1\\\mathbf p_1&1\\\vdots&\vdots\\\mathbf p_n&1\end{vmatrix}=0$$ and a normal vector to it is given by the generalized cross product $$\begin{vmatrix}\mathbf e_1&\mathbf e_2&\cdots&\mathbf e_n&1 \\ p_{11}&p_{12}&\cdots&p_{1n}&1 \\ \vdots&\vdots&\ddots&\vdots&\vdots \\ p_{n1}&p_{n2}&\cdots&p_{nn}&1\end{vmatrix}=0.\tag{*}$$

Equivalently, find a null vector of the $n\times(n+1)$ matrix formed by deleting the first row of the matrix in (*) and dehomogenize it by dividing through by its last component. This amounts to creating a system of linear equations by substituting the coordinates of the known points into the generic equation $a_1x_1+\cdots+a_nx_n=a_0$ of a hyperplane in $\mathbb R^n$. For large $n$, an efficient way to do this is to compute the SVD of this matrix and take the singular vector that corresponds to the least singular value. Because of roundoff and other sources of error, don’t depend on the singular value being exactly zero.