# Min supporting line for a set of points

I'm trying to solve exercises of the book "Computational Geometry in C" by O'Rourke. Could you please help me with this one?

Design an algorithm to find a line $L$ that:

• has all the points of a given set to one side
• minimizes the sum of the perpendicular distances of the points to $L$ Assume a hull algorithm is available.
• I'm a programmer but I'm naive about problems like this. (What you just read was a warning. :) What have you thought or tried thus far? – Bill Bell Oct 26 '16 at 20:32
• I think such a line should have one extreme point, (The extreme points of a set S of points in the plane are the vertices of the convex hull at which the interior angle is strictly convex, less than pi.) Is it an edge of convex hull? I have to prove any claim. – f44 Oct 26 '16 at 21:39
• Look for algorithms for "linear discriminant analysis" to see how other people have approached the problem. – Biswajit Banerjee Oct 26 '16 at 21:45
• @Jane95 Your hypothesis certainly ensures the first bullet is satisfied. It is likely on the right track, if not the correct solution. – spektr Oct 26 '16 at 23:53