A line is a best fit for a point set S in the plane if it minimizes the sum of the distances between the points in S and the line. Assuming a convex hull algorithm is available, find the best fit line for a given point set S in the plane. This is an exercise from book Discrete and Computational GEOMETRY. I'm trying to solve this problem for months. I know how to solve it with calculus and clever bruteforce. Analytic way to solve this problem is http://mathworld.wolfram.com/LeastSquaresFittingPerpendicularOffsets.html. I'm not interested a fast or optimal solution.
1
votes
Hello, welcome to StackOverflow! Can you please show what code have you tried so far?
– uv_
I want to understand an algorithm or idea
– Vnyemets
It is hard to see - how convex hull is related to optimal line...
– MBo
I think this algo is not optimal and fast but the problem is very interesting for me
– Vnyemets
Example: find the shortest width of CH and make line perpendicular to that width. Will be approximation for uniform distribution, but don't work for many cases (i.e. few points form CH, but a lot of others are inside and clustered)
– MBo
1 Answers
2
votes
Aim instead for the best-fit Chebychev line, which minimizes the maximum distance from the points to the line. This meshes better with convex hull properties.
PDF download lecture by Ion Petre.
