I have a 3D point cloud near the origin (0,0,0). All triples (x,y,z) are non-negative, which means that my points lie in the positive octant.

I know that the point cloud approximates a "concave" volume V, in the sense that the complement of V in the positive octant is convex.

How do I get the "concave" boundary of V, i.e., the convex hull of the complement of V?

The function convhull is not directly helpful of course. But is there a trick?

here is an idea: Any concave solid can be split summed as a collection of finite number of convex solids. I am personally unaware of any ways to do this.(I am sure something exists!). So I searched online and I found this on a different website:

http://social.msdn.microsoft.com/Forums/en-US/sqlspatial/thread/43e2f7da-3614-4887-80a5-52e7e337943f

If you asked me what I would use: it would be a brute force method of induction: I would start with four vertices and form a tetrahedron that contain no other points (choose 4 and then recurse if there are points that exist inside this, ignore the first choice thus avoiding unnecessary false edges). Such a construction should give rise to a tetrahedral solid that approximates the concave hull. I would like to shy away from answering the complexity of this algorithm. 

Dear Jens,

is a concave hull well defined at all? I imagine the 2d case of 4 points on the corners of a square and an additional point in the center. What is the concave hull?

Jan