Suppose there are n points in m dimention (n < m), and p+1 points are selected to form a simplex (p+1 < n < m, p+1 << m).
The p simplex volume is determined by Cayley-Menger Determinant:
$V^2 = \frac{-1}{(-2)^p (p!)^2} \det(C)$,
while C is $\pmatrix{0&e^T\\ e&B}$, and B is a (p+2)*(p+2) pair-wise distance matrix with a top row (0,1,...,1) and a left column (0,1,...,1)^T.
Now I want to replace the point $p_1$ in p with a point in {n-p} to maximize the volume, while keep other points unchanged. A straightforward way is to calculate det(C) for every point in {n - p}, but it might be slow if the set of {n-p} is huge.
I could exclude points in the original simplex hull (simplex with $p_1$), however there might be not many points exactly lay inside/on the simplex hull.
Are there ideas on how to quickly filter out points in {n-p}?
From a set of $n$ points in $\mathbb R^m$, we generate a (p-1)-simplex $S_{p-1}$ with vertices $\{\vec v_1,\vec v_2,...,\vec v_p\}$. By choosing another affinely independent point $\vec v_{p+1}$, we can generate a new p-siplex $S_p$. We have many choices of $\vec v_{p+1}$, and we want to find the one that maximizes the volume of $S_p$.
To do this, we can use a recurrence relation for the volume of simplices. Letting $V_p$ and $V_{p-1}$ be the volumes of $S_p$ and $S_{p-1}$ respectively, we have:
$$V_p=\frac hpV_{p-1}$$
Where $h$ is the "height" of $\vec v_{p+1}$ above the base.
Let $A$ be the affine span of $\{\vec v_1,\vec v_2,...,\vec v_p\}$ (the p-1 dimensional hyperplane containing all the points). If we choose any point in the span, such as $\vec v_p$, and subtract it from all of our points (this is a translation that does not affect the geometry of the problem), then A becomes a subspace (Which I'll call B) spanned by $\{\vec v_1-\vec v_p,\vec v_2-\vec v_p,...,\vec v_{p-1}-\vec v_p\}$. Also, the vector $\vec v_{p+1}-\vec v_p$ points from a point on the subspace to $v_{p+1}$.
We can thus find $h$ by finding the component of $v_{p+1}-v_p$ perpendicular to B. That is,
$$h=\left|\text{proj}_{B^\perp}(\vec v_{p+1}-\vec v_p)\right|=\left|\vec v_{p+1}-\vec v_p-\text{proj}_B(\vec v_{p+1}-\vec v_p)\right|$$
Since $m>>p$ (and thus $B^\perp$ is much higher dimensional than $B$), the second expression is more useful. The projection operator $\text{proj}_B$ can be expressed as a matrix $P$.
$$P=B(B^TB)^{-1}B^T$$
Where $B$ denotes a matrix whose columns are $\vec v_1-\vec v_p,\vec v_2-\vec v_p,...,\vec v_{p-1}-\vec v_p$. This gives us a compact expression for $h$.
$$h=\left|(I-P)(\vec v_{p+1}-\vec v_p)\right|$$
Since $I-P$ depends only on $\vec v_1-\vec v_p,\vec v_2-\vec v_p,...,\vec v_{p-1}-\vec v_p$, it only needs to be computed once. Finding $h^2$ for a particular choice of $v_{p+1}$ will require one matrix-vector multiplication and one dot product, and the choice that maximizes $h^2$ necessarily maximizes the volume.