9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You know the points are vertices of the polyhedron. Do you know the faces (polygons on the hull)? If so you can compute the volume rather easily (as a sum of "cone" volumes). $\endgroup$ – hardmath Jul 28 '13 at 20:02
  • 1
    $\begingroup$ A lazy way would be triangulating first, then adding up the volumes of the tetrahedra (very easy to compute). $\endgroup$ – Shuhao Cao Jul 29 '13 at 1:42
  • $\begingroup$ @hardmath: No. I know that if I knew the facet shapes it would be easy. $\endgroup$ – Victor Liu Jul 29 '13 at 20:59
  • $\begingroup$ @Shuhao Cao: Is there a simple triangulation algorithm for this special case? Generally 3D tetrahedralization algorithms are quite complicated, and I expect to need to solve this problem thousands or millions of times. $\endgroup$ – Victor Liu Jul 29 '13 at 21:00
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

convhull

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$.

$\endgroup$
  • $\begingroup$ BTW the test is done on my old 2007 Core 2 T61p. $\endgroup$ – Shuhao Cao Jul 31 '13 at 23:55
1
$\begingroup$

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.

$\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.