I am following along Rourke's book and I am trying to do the excercies mentioned in this SO post:
Design an algorithm to find a line 𝐿 that:
has all the points of a given set to one side
minimizes the sum of the perpendicular distances of the points to 𝐿 Assume a hull algorithm is available.
Just like the OP in that question I also solved the problem when the set is just the convex hull. You can easily make an h log h algorithm for the hull that finds you a line and a point in the hull such that their distance is the smallest among all possible such pairs.
- start a given line in the hull
- Look at the point that is h / 2 indices away in the CCW direction
- if both points adjacent to this point are closer to the line, mark this line point pairing.
- else, see which point is farther away and look at the median index of the range between your line endpoints and the point you just found.
- Repeat until you've found the farthest point from the line.
- Repeat for every line to find the line point pair that minimizes the distance.
The search operation is logarithmic so this takes $h \log h$. If your set of points is the hull I am 100% sure this minimizes the distances.
But I am not convinced that this is the optimal solution for any set of points however.
Consider a really, really, really, narrow triangle. let $P_1, P_2, P_3$ be its vertices such that $P_2$ is the point that minimizes the convex hull distance.
Now let's add a billion points along the edge $P_2, P_3$ such that no 2 points share the same coordinate.
The convex hull is the same. But the edge that you should pick is $(P_2, P_3)$.
Am I wrong?