# 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? 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. 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. Oct 26 '16 at 23:53

## 1 Answer

You're allowed an algorithm that computes the hull. If this means an algorithm that computes the convex polygon then I would say consider the lines defined by adjacent points on that polygon. I think it's possible to prove that one of those lines is the one required. Therefore, the required algorithm is simply to iterate through them, calculate sums of distances and select 'best'.

• That's basically what I came up with. You compute the maximum distance of a point on the hull from the line defined by adjacent points on the hull, and then select the line where the distance is minimum. May 25 '17 at 17:13