2
$\begingroup$

The wikipedia entry for convex hull shows a 2-d example of a random set of points on x-y plane, and the "elastic band" solution that bounds the points with the convex hull solution. The definition of the solution seems to be the one that achieves a minimum perimeter length, although I don't think that is explicitly stated. Nor is it stated that the solution might result (or does result) in the maximal area solution (among a set of possible solutions).

I'm trying to understand, when applied to a 3-D set of points, if the convex hull solution is attempting to either (a) give a solution with the minimum surface area, or (b) give a solution with the maximal enclosed volume?

If (a), then is the resulting enclosed volume always turn out to be the maximal one? Or is that coincidental?

Additional clarification / example:

These are the x,y,z coordinates of 8 points:

(1) 49.186, 42.474, -8.54 (2) 40.010, 37.828, -6.929 (3) 46.212, 46.602, 2.459 (4) 39.167, 41.661, 0 (5) 51.601, 32.308, -4.584 (6) 44.459, 30.948, -4.876 (7) 51.316, 35.726, 5.61 (8) 42.176, 32.551, 1.811

This is the geometric center of the above points:

(9) 45.51588, 37.51225, -1.881125

The first iteration of computing volume by arranging the following 12 triangular surface facets:

(node # for each facet, and the corresponding quadrahedral volume using node #9)

1, 2, 5, 83.96766 2, 5, 6, 41.32112 1, 2, 3, 101.5469 2, 3, 4, 51.66822 1, 3, 5, 87.59101 3, 5, 7, 83.91972 5, 6, 7, 65.09879 6, 7, 8, 62.75732 2, 4, 6, 39.78588 4, 6, 8, 45.75238 3, 4, 7, 83.37383 4, 7, 8, 75.34743

Total volume: 822.13026

That is just one out of 64 possible arrangements of surface facets. The volumes of all 64 arrangements are (sorted from smallest to largest volume, showing integer results for brevity):

773 777 783 785 787 789 795 798 822 824 825 825 827 828 831 833 833 835 835 835 837 837 837 838 839 840 843 845 847 847 849 850 872 873 875 875 876 878 882 883 884 885 885 885 886 887 887 888 888 890 893 895 897 897 898 900 923 927 933 935 936 938 945 948

A convex hull algorithm (offhand I don't know which one) gives an answer that exactly matches the largest volume (948.78). The algorithm determines it's own facet set (ie not specified by the operator). When run on a time-series of data where the coordinates are changing slightly, the convex hull consistently gives the largest volume (out of 64 possible volumes). I believe that the corresponding surface area is almost always the smallest (again out of 64 possible outcomes).

So I was wondering if the proper way to code a convex hull algorithm is to seek a solution with the smallest surface area, instead of a solution that yields the largest volume.


Just to add - am I correct in thinking that the "convex" part of convex-hull is meant to indicate a positive (convex) surface curvature, and not negative (or concave) curvature? In other words (in a 3-D case) if a membrane is stretched around a set of points (or around a dumb bell) that any cutting plane that is passed through the convex-hull solution must give a projected 2-d path with a positive curvature at all points on the path. A dumb-bell with a pinched hull membrane would exhibit negative curvature and hence could not be called a "convex" hull. Does this make sense? If so, the maximal-volume solution is the "correct" solution for the convex hull surface.

$\endgroup$
  • 1
    $\begingroup$ You should always supplement "maximal" or "minimal" by a "among...". It is necessary and it will help you. For example in 3D, it can not be "maximal volume among the convex sets containing all the given sets"... because there is no such maximum... But there is a minimum in this case. $\endgroup$ – Jean Marie Feb 6 '16 at 0:34
  • $\begingroup$ Relevant previous question: Convex Hulls vs Shrink Wrap $\endgroup$ – Rahul Feb 6 '16 at 0:37
  • $\begingroup$ Each of these 64 solutions could be a "hull" surface that bounds the 8 points The convex hull is unique. $\endgroup$ – dxiv Feb 6 '16 at 1:12
  • $\begingroup$ As explained in comments under the linked question, the minimum-area surface enclosing a dumbbell shape is "pinched" in the middle, whereas the convex hull is cylindrical. So the answer about minimum surface area is definitely no. The "maximum" question is still completely unclear. And how would the total area of the 12 facets or volume of the 12 tetrahedra ever be different from the area and volume of the box in your example? Suppose the box is a unit cube with vertices at $(0,0,0)$ and $(1,1,1)$, how would your construction come up with anything other than area=6, volume=1? $\endgroup$ – David K Feb 6 '16 at 1:51
  • $\begingroup$ I added some comments and links to my answer, but at this point it sounds like you want to work out your own 3D convex hull algorithm, yet you haven't provided enough details to figure out what exactly you are trying to do. $\endgroup$ – dxiv Feb 6 '16 at 19:25
1
$\begingroup$

The convex hull is the smallest convex body that contains the given set. Any other convex body that contains the set will necessarily contain its convex hull.

A convex body enclosed in another has both smaller area and smaller perimeter in 2D, or smaller surface area and smaller volume in 3D. So the convex hull is also the smallest enclosing convex body in the sense of "size".


[EDIT] Following the additional clarification / example edited into the original question, I am no longer sure that you are asking about the convex hull, which is the unique body defined as the intersection of all convex bodies containing the given set of points, or perhaps asking about some other/special convex polyhedron that's just "close enough" to the convex hull.

If it's about the convex hull, then again that's the smallest convex body containing the given points. If you want to reformulate it as an optimization problem, then the convex hull is the convex body with the minimum volume (or minimum surface area, for that matter) that contains the points. To phrase it the other way around, any body with a volume (or surface area) smaller than the convex hull is either (a) not convex, or (b) does not contain all points.

P.S. Some references, maybe useful.

More discussion and pointers are on StackOverflow at How to find convex hull in a 3 dimensional space.

Reference source code for determining 3D convex hulls is available from Qhull (Qhull code for Convex Hull ... - C/C++) and CGAL (3D Convex Hulls - C++).

An online Java demo can be found on Thomas Diewald'page Convex Hull 3D - Quickhull Algorithm (online Java demo), and a full Java package can be downloaded from John Lloyd's page QuickHull3D: A Robust 3D Convex Hull Algorithm in Java.

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