1
$\begingroup$

In my experiment I need to compute hypervolume/area from a set of points,

let's start with a base case --

Triangle: In this case, I have 3 points in a 2D space and they make a triangle, $p_1 = \{x_1, y_1\}$, $p_2 = \{x_2, y_2\}$ and $p_3 = \{x_3, y_3\}$. Assume $p_3$ is the apex. The area of the triangle can be computed as $\frac{1}{2}|\mathbf{v_1} \times \mathbf{v_2}|$, where $\mathbf{v_1} = \{(x_2 - x_1),(y_2 - y_1)\}$ and $\mathbf{v_2} = \{(x_3 - x_1),(y_3 - y_1)\}$

Tetrahedron: In the case for 3D space, I will have 4 points, $p_1 = \{x_1, y_1, z_1\}$, $p_2 = \{x_2, y_2, z_2\}$, $p_3 = \{x_3, y_3, z_3\}$ and $p_4 = \{x_4, y_4, z_4\}$. $p_1$, $p_2$ and $p_3$ make up the base and $p_4$ is the apex. The volume can be computed as $\frac{1}{6} |\mathbf{v_1} \cdot (\mathbf{v_2} \times \mathbf{v_3})|$, where $\mathbf{v_1} = \{(x_4 - x_1),(y_4 - y_1),(z_4 - z_1)\}$, $\mathbf{v_2} = \{(x_4 - x_2),(y_4 - y_2),(z_4 - z_2)\}$ and $\mathbf{v_3} = \{(x_4 - x_3),(y_4 - y_3),(z_4 - z_3)\}$.

generalization --

N-dimension: In the case for n-dimensional space, I will have $1$ n-dimensional point as the apex and I will also have $n$ numbers of n-dimensional points that form the base (hyperplane). The solid that I need to form is an n-dimensional hyper-hedron (I am not sure if it's the right word) and I need to compute it's volume.

How do I generalize the (hyper-)volume computation for the n-dimensional hyper-hedron ?

$\endgroup$
2
  • $\begingroup$ what do you mean by $n-d$ point? $\endgroup$ – hjhjhj57 May 28 '15 at 3:55
  • $\begingroup$ it's n-dimensional, corrected, sorry I don't know the exact math term for that. $\endgroup$ – ramgorur May 28 '15 at 4:09
2
$\begingroup$

I think you are looking for the volume of an $n$-dimensional simplex. If you have $n+1$ points in $n$ dimensions (where the points are given as vectors $v_0,v_1,\dots,v_{n}$), then the formula for the volume is given by

$$\left|\frac{1}{n!}\det\left[\begin{matrix}v_1-v_0\\v_2-v_0\\\vdots\\v_{n}-v_0\end{matrix}\right]\right|$$

$\endgroup$
4
  • $\begingroup$ where does the $1/n!$ term come from? $\endgroup$ – hjhjhj57 May 28 '15 at 4:10
  • $\begingroup$ thanks, could you please give the matrix form for the $\det(v_1-v_0,v_2-v_0,\dots,v_{n+1}-v_0)$ term ? I don't quite understand what does it mean by $\det(a_1, a_2, a_3, \ldots, a_n)$ $\endgroup$ – ramgorur May 28 '15 at 4:28
  • 1
    $\begingroup$ @ramgorur Sorry it was unclear - I have now edited. Each row $i$ is defined by the difference between $v_i$ and $v_0$ (I also fixed a typo - the last entry should have $v_n$ instead of $v_{n+1}$). This is slightly different from the Wikipedia definition which uses the vectors I give as rows in their columns, but this doesn't affect anything when we take the determinant. $\endgroup$ – Peter Woolfitt May 28 '15 at 7:37
  • $\begingroup$ @hjhjhj57 That term occurs because if we just take the determinant then it's the volume of a parallelepiped. I just use the intuition in three dimension where it is the difference between a tetrahedron and a parallelogram prism. $\endgroup$ – Peter Woolfitt May 28 '15 at 7:41
1
$\begingroup$

Each dimension requires an adjusting factor because you're going for a "triangular" simplex instead of a "square" one. 1D Line segment is 1/1. Area of a 2D triangle is 1/2 the height times its base (line segment). Volume of a 3D tetrahedron is 1/3 the height times the base (triangle), which we just said was 1/2 of its height times its base. So we're up to 1/(3*2*1) = 1/(3!) already. Hypervolume of a 4D "hyper-tetrahedron" simplex is going to be 1/4 its height times its base (tetrahedron), which we just said was 1/6; so we're up to 1/(4!) so far. Etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.