can you formally identify this geometry optimization problem?

June 2, 2006 10:45 PM

given a set of points from an n dimensional metric space, construct a surface of minimal volume which contains these points.

the vertices of the surface do not have to be taken from the set. an efficient approximation would suffice.

posted by paradroid to Science & Nature (13 answers total)

Does the surface have to be convex? If so, I think you're looking for convex hull algorithms.
posted by clarahamster at 10:48 PM on June 2, 2006

Yes, that's a convex hull problem. The thing is (and I've been doing some research on high-dimensional convex hull algorithms, so I'm pretty confident about this) that the best algorithms for getting an exact convex hull are something like O(n ln n+n^d), where n is the number of points and d the number of dimensions. In other words, it's an exponential problem.

There are, supposedly, ways of approximating the surface, and I was pointed to Piotr Indyk as someone who's done research into approximations of high-dimensional computational geometry problems, but so far I haven't found anything on his web site that'd help with volume approximation. He did his thesis on nearest-neighbor approximation, but I don't see a good way of using that to give you volume. I sent him an email about a week ago, but haven't gotten an answer back...

I'm very much hoping you find an answer to this, because I need an algorithm like this too.
posted by wanderingmind at 11:08 PM on June 2, 2006

Response by poster: the surface does not have to be convex, but it does have to be connected.
posted by paradroid at 12:26 AM on June 3, 2006

The surface formed by the intersection of the exterior of the convex hull with the interior of the convex hull trivially has zero volume.
posted by zaebiz at 12:57 AM on June 3, 2006

The above is obviously not the full answer but you can clearly see it is trivial to construct a surface of zero volume.
posted by zaebiz at 12:59 AM on June 3, 2006

More information is needed. When you say metric space, do you mean R^n? In a general metric space, there is no intrinsic notion of volume.

Also, do you know anything about the set of points? Is it finite? Open, closed, compact?

Finally, what exactly do you mean by a surface? Do you mean an (n-1)-dimensional submanifold?

What is the context of this question?
posted by number9dream at 1:14 AM on June 3, 2006

Response by poster: yes, R^n

the set of points is finite.

yes, the volume must be greater than zero.

yes, by surface i mean a submanifold, specified as a list of points.
posted by paradroid at 1:31 AM on June 3, 2006

Perhaps there's something in the compendium of NP optimization problems.
posted by donut at 1:31 AM on June 3, 2006

I don't think you've given enough information yet. What dimension do you want the submanifold to be? Given a finite number of points, I could give you an embedded smooth manifold of dimension 1 (i.e. a curve) through the points. It would have nonzero "volume" as a manifold, but volume here would just be arclength. Surely this isn't what you mean.

Do want a dimension n submanifold? In this case, it still sounds like you're asking about a convex hull. But if the submanifold only has to be connected and not convex, you can find an open submanifold (or submanifold with boundary) containing your points of arbitrarily small volume (since there are only finitely many points). Thus, there is no such submanifold with minimal volume.

Also, "by surface i mean a submanifold, specified as a list of points"? Any (nonempty) submanifold of dimension greater than 0 has an infinite number of points. It would be a bit impractical to list the points.

Finally, do you want a topological submanifold, or a smooth submanifold?
posted by samw at 1:49 AM on June 3, 2006

Response by poster: the enclosing volume should be n dimensional.

by "specified as a list of points" i don't mean the entire set, i mean a finite set of points which defines the volume, ie a vertex list.

that list of np problems was neat but didn't have this one in it. thanks tho.
posted by paradroid at 2:15 AM on June 3, 2006

gau? is that you? or is it just a really bizarre coincidence that my buddy was asking me for help with this very same problem at a bar the other night?
posted by garethspor at 2:43 AM on June 3, 2006

I think you still need to define the problem better. If the enclosing surface doesn't have to be convex, then the obvious minimal-volume answer is a zero-volume surface (or arbitrarily-small-volume surface). It sounds like this isn't acceptable, so you need to figure out why it isn't acceptable, and state that reason; without a well-posed question, you're not going to get an answer you like.

A way to approach it might be to figure out what you're trying to optimize. You want minimum volume. Maybe you also want to minimize or maximize something else? Minimum surface area? Minimum surface curvature?
posted by hattifattener at 10:40 AM on June 3, 2006

Response by poster: i think what i want is sometimes called a rubber band or shrinkwrap surface, ie the surface that would result if you put the points inside a large sphere and shrunk the sphere to just contain the points. i am not sure that is well defined.

maybe this is in fact a convex hull, i will read more. are there other common variations on this problem other than convex?
posted by paradroid at 10:17 PM on June 3, 2006