1

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?

0
1

Let me start by pointing out the errors in the two algorithms you described:

  • In both algorithmic scetches, there is the same error of assuming the maximum pairwise distance of the points in the 2D plane would be the diameter of the smallest enclosing circle. Looking at just three points, it should be clear why this is not correct:

    Instead, the diameter of a circle enclosing all points must be identical to the distance of either two points, or identical to the circle diameter of a subset of three points, where all the three points are on the convex hull of the full set (in 2D). This gives you a straightforward (partially) brute-force solution for the smallest enclosing circle problem (just iterate about over all pairs and triples of the points on the convex hull). See Smallest-Circle-Problem) for more sophisticated approaches.

  • In the first scetch, there is the error of assuming the length of the cylinder must be identical to one of the pairwise distances of the points, which is not a necessary condition. The two points with maximum distance could be placed diagonally at the top and bottom of the cylinder, so the cylinder length being smaller than their distance:

    Hence I don't think one should start with the general case first, I am pretty sure it is harder than the specialized case.

IMHO you had a good start with the second algorithmic scetch: finding all triplets which are suitable for a base side reduces the problem to a finite set of cylinder axis directions, and solving the problem when the axis direction is known is a lot simpler. Your idea of continuing with the projection to that plane is fine, but with a corrected version of the "enclosing circle" algorithm (see above). That should fix your second algorithm.

As an optimization, you could try to implement an algorithm for the triangulated 3D convex hull, and then check only the planes given by the triangles on the hull. That should reduce the number of planes to a large degree.

Beware, implementing a the 3D convex hull algorithm, or an efficient 2D smallest-enclosing circle algorithm may still be a challenge. An O(N^4) solution for the second problem is described here, a more sophisticated one is here.

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.