(change theme to light one if formulae are not recognizible)
To strictly determine whether the point lies into the simplex or no you only need to know a signs of at maximum d + 2
determinants of d * d
size.
Let:
then we can construct a matrices (j,k
index means: exclude j
row and subtract vector from origin to point k
from each of d
remaining rows; all the left hand sides in rows defines a facet lying against j
vertex):
Determinant of the above matrix is d!
times d
-dimensional oriented hypervolume of a simplex, constructed from points involved in the formula (strictly saying is the oriented hypervolume of a parallelotope, whose edges are given by the matrix rows).
If point is inside the simplex, then all the below equations is true (matching the orientation (sign of oriented hypervolume) of j
and 0
pair of points relative to a facet):
but we can note, that
So we can calculate only one determinant from left hand side of comparison (?
):
and assume, that sign flips for next j
s.
Therefore, we should to compute at least 2
determinants of d*d
matrices, and maximum d + 2
(of A1,1 and of Aj,0 for all j
in {1, 2, ..., d + 1}). If sign is not matched on some step, then the point is outside of a current facet of the simplex, and, thereby, out of the simplex at all.
ADDITIONAL:
If some of the right hand side determinants are zero, then the point is coplanar to planes of corresponding facets.