How to get the smallest diameter of a cicular pipe enclosing many points in 3D space?

I wanted to know the mathematics and then use Matlab to do it.

In 2D plane, for example, if there are three points, then there would have three pipes (pair of parallel lines) that could enclose all points, then what I need the smallest diameter of the pipe would be the smallest distance between the parallel lines in this 2D case.

Thanks...

[Matt J]

In your 2D example, what do you mean by three pairs of parallel lines? Aren't there an infinite number pairs that could enclose the points? Or are you just eliminating pairs you know are not optimal?

[Walter Roberson]

A diagram would help.

http://www.mathworks.com/matlabcentral/answers/7924-where-can-i-upload-images-and-files-for-use-on-matlab-answers

[Matt J]

Do you have FMINIMAX?

Answer 1

[Image Analyst]

Why do you have three pairs of parallel lines? A point has no thickness so they'd be single lines. Now, if you had balls (believe me, no pun intended) at those points and lines on each side of the balls, then you'd have three sets of parallel lines.

Next, I don't understand the connection between diameter and distance (length). Assuming they are balls and not points, why does diameter of the "pipes" (i.e. the separation between the parallel lines) have to be equal to the length of the shortest pair of parallel lines? I don't see how they are related. To me, they're totally independent. The diameter is the diameter of the ball and has no relation to how far apart the balls are.

Finally, a stab in the dark at a possible solution. You aren't by any chance talking about the convex hull are you? Or wanting the smallest enclosing circle like in John's File Exchange Submission: http://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects

After re-reading your post, I think you want to use John's "minboundcircle" routine, am I right?

[Walter Roberson]

smallest enclosing circle was my first thought, but the bit about having "three pipes" threw me off.

I wonder... is "pipe" being used to designate the || symbol meaning "parallel" ??

[Image Analyst]

It's unclear. The other thought I had was he wants to find the largest set of parallel lines that will go between the point, which is essentially what Support Vector Machine (SVM) classification does, but I thought that was less likely, but who knows?

[Matt J]

I think the OP has a cloud of points in 3D space and wants the narrowest cylinder enclosing them. Too bad John's package doesn't have a "minboundcyl", but minboundcircle could probably be extended to cylinders when used in conjunction with the Optimization Toolbox (or maybe even fminsearch).

Answer 2

[Matt J]

Here's my idea (untested) for extending minboundcircle to create a "minboundcyl". It assumes that the 3D points are the columns of the matrix "cloud".

   fun = @(x)objfun(x,cloud);   

      [U,S,V]=svd(bsxfun( @minus,cloud,mean(cloud,2)  ).',0);
   InitialGuess=V(:,1);

   cylinderAxis =  fminsearch( fun, InitialGuess);
   [cylinderRadius,cylinderCenter]=fun(cylinderAxis);

function [radius, center]=objfun(x,cloud)

    x=x(:).'/norm(x);
    B=null(x);  

    xy = B\cloud; %projection onto plane

    [center,radius] = minboundcircle(xy(1,:),xy(2,:));

     center=B*center(:);

end