2
$\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
    Commented May 28, 2015 at 3:55
  • $\begingroup$ it's n-dimensional, corrected, sorry I don't know the exact math term for that. $\endgroup$
    – ramgorur
    Commented May 28, 2015 at 4:09

2 Answers 2

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
    Commented May 28, 2015 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
    Commented May 28, 2015 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$ Commented May 28, 2015 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$ Commented May 28, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .