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.
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?