# Find two horizontal lines to minimize distance to scattered points

I am having trouble with a coding question that I found practicing for a interview:

A scatter graph of points on a page, draw two horizontal lines (these lines are parallel) across the page such that the perpendicular y distance to a line from all points is minimized. Count the total distance from each point to the line that is closest (Only count the distance from each point to the closest line, ignore the longer distance, when the distance is the same, pick either one). Describe an algorithm for finding these two lines.

My approach:

I have considered brute forcing this by checking all possibilities in intervals of 1 starting from the highest y axis ending with the lowest y axis of the points, but this is perhaps not the most optimal way. I have also considered splitting the points into two groups based on y axis, however there are some edge cases that will fail.

Does anyone know a more efficient way to do this?

• – gnat
Nov 27, 2018 at 5:57
• "all possibilities in intervals of 1"? Why 1? Aren't the coordinates supposed to be double values? Nov 27, 2018 at 6:32
• @DocBrown The sought lines are horizontal. This is a 1D problem. Nov 27, 2018 at 6:48
• @NickAlexeev: obviously, but that does not make it a discrete integer problem. Nov 27, 2018 at 6:49
• @DocBrown It is a discrete problem because there is an integer number of points to consider. This can be seen as a clustering problem; each point either belongs to cluster A or B → I can enumerate all permissible clusterings, giving rise to Kain's O(n log n) solution. The non-discrete version would be if I had point densities rather than discrete points, but that would be extremely hard unless the density has an analytical form that's once differentiable.
– amon
Nov 27, 2018 at 14:39

Yes there is a much more efficient way to do this. Off the cuff I can write an O(N log(N)) algorithm. As this is a test question, the point is not solving it it is the process of solving.

The problem you seem to have is a perspective issue. Try reducing the size of the problem down.

• How would you solve this for two points?
• How would you solve this for three points? four points? five points?
• Given that you've already solved this problem for K points, can you solve it for K+1 points?
• Does that K+1 point need to have certain properties?
• Would receiving the points in a particular order make it easier to solve?
• Would considering the points one, two, three at a time make it easier to solve?
• How does each line behave as a point is added?
• Can you take advantage of that behaviour?

At this point you'll probably have worked out if and how to sort the points, how they are picked, and how many points you'll consider at once. You will know how to update the solution for the next point, and you'll know that your answer is correct after having considered all points.

• The idea of solving problems this by induction is not bad in general. However, I doubt it will work well for this specific problem (but maybe I am just to blind to see it). Nov 27, 2018 at 6:52
• There is a way to construct this by induction take some time and think it through. Perhaps find a copy of Computational Geometry - Algorithms and Applications Nov 27, 2018 at 7:16