Hi folks,

I am assigned a part of a child gaming project, and I am to solve the following problem in a VERY narrow deadline; here it is: "Given a set of 100,000 points in the 3D space, select 10% of these points such that the polyhedron made up of these selected points has the highest possible volume."

I have thoroughly tried to use a MAXIMUM-CLIQUE approximator as a clue, but it seems to have a much much simpler solution of which I am not aware. Anyone knows an AI way to solve it? Thanks.

Probably better served in the math forum. I'll wait to see if anyone here answers prior to moving it, though.

Find the centroid of the point cloud, then locate the 10% of points furthest from it.

How is the volume of the polyhedron defined? Is it based on the convex hull of the selected points?Can you use less then 10% if necessary?

Find the centroid of the point cloud, then locate the 10% of points furthest from it.

Take 0.9N points uniformly distributed on the unit sphere and 0.1N points uniformly distributed on the circle of radius 10 and center the origin in the {z = 0} plane. Your solution would select the 0.1N points on the circle, even if their convex hull has zero volume (the points are all coplanar)*. I suspect it would give a quite good solution in the average case though.


* I think the solution in that case would be to select all but two points in the circle to maximize the area of their convex hull and then take the points with the maximum and minimum z.

Eh, I figured there was an easy way to defeat that approach... it was meant more as a starting point for how to think of heuristic solutions than a true answer :-)

Find the centroid of the point cloud, then locate the 10% of points furthest from it.

It's easy to imagine a point cloud organized such that this would fail.

Simplify the problem by making it a cloud of 10 points and say we're trying to find 4 points such that the tetrahedron has maximum volume. Then put 6 points scattered around the centroid and put 4 outside such that they form a degenerate tetrahedron of very small volume.

Edit: I apologize, I just saw that apatriarca just described a similar problem with the technique.

What if you were to divide an imaginary sphere containing the point cloud and centered at the centroid into 1,000 sectors, and select the point in each sector that is furthest from the centroid?

Eh, I figured there was an easy way to defeat that approach... it was meant more as a starting point for how to think of heuristic solutions than a true answer :-)

Sure.. I only wanted to point out it wasn't a "correct" solution. I think a better solution is to consider the convex hull of the point cloud and gradually eliminate the point of the convex hull which cause the minimum volume loss. I'm not sure if it might fail for some cases though.

The first thing that comes to mind is simulated annealing. Start with a random subset of the desired size and then try changing a random point A in the subset by a random point B not in the subset: If the volume increases, accept the change; if it doesn't, accept the change with some probability that depends on how bad the change in volume is, and on a parameter called "temperature".

P(A -> B) = exp((volume_with_B-volume_with_A)/temperature)

I think if you lower the temperature slowly enough, the probability of ending up at the optimal solution is arbitrarily high. And if you rush it, you still get a decent approximation.

[EDIT: You only need to pick B from the points that are not in the convex hull of the subset. That's probably an improvement.]

What A Brain in a Vat proposed isn't even well defined. What do you do in sectors with no points?