Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull.
More precisely, I'm given a small set of points (say, 10-15) in 3D, all of which are known to lie on the convex hull of the point set (so they all "matter" and define the hull). I only want to compute the volume of the hull, I don't care about computing the actual polyhedron. Is there an efficient algorithm to do this?
I'd be surprised if you can beat the suggestion of Shuhao Cao: compute the hull and then the volume once you have a triangulation of the hull. You could compute the hull with the $O(n^2)$ incremental algorithm, or the gift-wrapping algorithm. If you really want easy code, you can simply write an $n^4$ loop over all possible triangles to see if they are on the hull. For $n=15$, this is still pretty fast, and you can easily implement shortcuts. Once you have all the triangle faces, then pick one vertex $v$ and make a tetrahedron with each triangle $T$ and $v$. Its volume is a $4 \times 4$ determinant in the vertex coordinates.
A small test in MATLAB, for number of vertex $N = 100$, each component is a uniform random number in $[0,1]$:
N = 100;
p=rand(N,3);
tic;
T = delaunayTri(p(:,1),p(:,2),p(:,3));
t = T.Triangulation;
e1 = p(t(:,2),:)-p(t(:,1),:);
e2 = p(t(:,3),:)-p(t(:,1),:);
e3 = p(t(:,4),:)-p(t(:,1),:);
V = abs(dot(cross(e1,e2,2),e3,2))/6;
Vol = sum(V);
time_elapse = toc;
Result:
time_elapse =
0.014807
Vol =
0.67880219135839
I would say it is reasonably fast, if you wanna run it $10^6$ times, it only takes less than 3 hours. Here is what it is like:
Also I want to mention that in Professor O'Rourke's post he mentioned using determinant to compute tetrahedra's volumes, yet here I prefer using triple product. It is a naturally vectorized operation, more scalable than the built-in routine of determinant (or you can expand a $4\times 4$ determinant by hand :p). Here is another test for $N=10^5$, the result is
time_elapse =
3.244278
Vol =
0.998068316875714
with tetrahedra number $\approx 7\times 10^5$. Notice the total volume is pretty closed to $1$ for there are too many points clustered in $[0,1]^3$.
From Komei Fukuda's Polyhedral Computation FAQ:
2.23 Is there any efficient algorithm to compute the volume of a convex polytope in $R^d$?
It is known that computing the volume of a V-polytope (or H-polytope) is #P-hard, see [DF88] and [Kha93]. There are theoretically efficient randomized algorithms to approximate the volume of a convex body [LS93] but no implementation seems to be available. There is a comparative study [BEF00] of various volume computation algorithms for convex polytopes. It indicates that there is no single algorithm that works well for many different types of polytopes.
[DF88] M.E. Dyer and A.M. Frieze. The complexity of computing the volume of a polyhedron. SIAM J. Comput., 17:967-974, 1988.
[Kha93] L.G. Khachiyan. Complexity of polytope volume computation. In J. Pach, editor, New Trends in Discrete and Computational Geometry, pages 91-101. Springer Verlag, Berlin, 1993.
[LS93] L. Lovasz and M. Simonovits. Random walks in a convex body and an improved volume algorithm. Random structures & algorithms, 4:359-412, 1993.
[BEF00] B. Bueler, A. Enge, and K. Fukuda. Exact volume computation for convex polytopes: A practical study. In G. Kalai and G. M. Ziegler, editors, Polytopes - Combinatorics and Computation, DMV-Seminar 29, pages 131-154. Birkhauser, 2000.
This may seem to bury the specifics of the 3D problem among difficulties of higher dimensions, despite the title of the Dyer and Frieze paper. From their Abstract: "We show that computing the volume of a polyhedron given either as a list of facets or as a list of vertices is as hard as computing the permanent of a matrix."
A 1991 paper by Jim Lawrence, Polytope Volume Computation, can be read online and has some references for the specifically 3D case. He writes, "The method in the present paper avoids triangulation of $P$ or of its boundary." Also the algorithm described in that paper seems appropriate for your situation as it expresses "the volume of $P$ as a sum of numbers $N_v$, one for each vertex $v$ of $P$. These numbers are easy to compute, so the difficulty of the procedure is mainly enumerating the vertices of $P$." The difficulty probably translates in your situation to finding an expression for $P$ as the solution of a system of linear inequalities $P = \{x \in \mathbb{R}^3 : Ax \le b \}$.
If you already know such an "intersection of half-spaces" expression for $P$, then perhaps it will permit a fairly fast computation.
