algorithms – Minimize volume of cylinder that covers a clusters, with constraints

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.