Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
A few hours ago i turned in my entrance exam, and i am very qurious 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 an cylinder that covers all stars, the cylinder can be in any direction.
Atleast 1 base of the cylinder must have atleast 3 stars.
There is at most 1000 stars.
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 leght 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 3 pairs of points that spans 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 elimate the inner points by using convex hull or similar. Would my solution work, or could you suggest a more eligant solution?