A few hours ago I turned in my entrance exam, and i am very curious about this last problem.
Given a cluster of stars each x, y, z range between -1000 to 1000. No four stars are coplanar.
Find the minimum volume of a cylinder that covers all stars, the cylinder can be in any direction. At least 1 base of the cylinder must have at least 3 stars. There are 1000 stars at most.
I first tried to solve the general case without the restriction of 3 stars, with the following
- Find two points with largest distance, this line goes through the center of the cylinder, and its lenght is the length of the cylinder
- Make a plane whose normal goes through that line
- project all points to that plane
- Find the smallest enclosing circle for all points, by taking largest distance between two points, this is your diameter.
- Calculate the volume
For the actual problem with constraints my idea was the following.
Find all tuples of 3 of points that span a plane.
Sort away all planes that have points on both sides, everyone else is the points on the outer boundires.
Take a plane and move it along its normal until all the points have moved to the other side, to find the length of the cylinder.
Project all points to the plane, and then find the smallest circle by taking the diameter to be the longest distance between pairs.
Compare volume for each plane and pick the smallest volume.
My solution feel very "brute force"-ish, and I was playing with the idea to eliminate the inner points by using convex hull or similar. Would my solution work, or could you suggest a more elegant solution?