Enclosing points between two parallel lines or surfaces?

Hi All - I'm trying to write some Matlab code to enclose a set of points between two parallel lines. Say, I have a 100 points (x,y). All values of x lie between 0 and 1, eg,

(0, 102) (0.01, -31) (0.2, 6)

etc

I have no idea in advance of the min or max of y.

How can I mathematically determine a pair of parallel lines, y1=mx + c1 and y2=mx+c2 which enclose all of the points? We seek to do so such that we minimise the difference between them, ie the distance c1-c2.

I seem to remember seeing an example of this using La Grange Multipliers in relations to SVMs. Is anyone familiar with this or any other simple solution for this type of problem?

Answer 1

[Jan]

For such a small set of points, you can find the convex hull at first and then search the minimal distance between each line and all other points. The convex hull will have between 3 and 99 lines, such that 99*98 distances between a point and a line are required only.