>One further thing to keep in mind: a method in which you select >the best of N-1 lines is O(N^2), because calculation of the sum >for each line is O(N). That means such a method isn't practical.
The most efficient algorithm proposed so far has complexity O(N) _times_ the complexity of a distance sum calculation.
However, a distance sum calculation by its very nature is O(N). so if each one of the distance sum calculations has to be done separately, and if each one is O(N), then, as you indicate, the whole task is O(N^2).
It seems unlikely that you can do better.
But do you now at least acknowledge my previous claim that there is an optimal bounding line which passes through two consecutive points of the convex hull?