1

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.

Vnyemets
  • 11
  • 2
  • 2
    Hello, welcome to StackOverflow! Can you please show what code have you tried so far? – uv_ Jan 17 '19 at 08:44
  • I want to understand an algorithm or idea – Vnyemets Jan 17 '19 at 08:56
  • It is hard to see - how convex hull is related to optimal line... – MBo Jan 17 '19 at 09:16
  • I think this algo is not optimal and fast but the problem is very interesting for me – Vnyemets Jan 17 '19 at 09:21
  • 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 Jan 17 '19 at 09:26
  • check this [Given n points on a 2D plane, find the maximum number of points that lie on the same straight line](https://stackoverflow.com/a/20888844/2521214) out – Spektre Jan 18 '19 at 08:41
  • @Spektre how does that task link with this? – Vnyemets Jan 18 '19 at 10:07
  • @Vnyemets Its a fast line regression from 2D point cloud ... its probably not exactly your task as you got convex hull constraint (hard to say what you mean by that as you did not show input and output data/image/sketch or whatever) but you can use ideas from it to speed up your "Brute force" approach. – Spektre Jan 18 '19 at 10:34
  • @Vnyemets after your last edit the question is unclear ... what do you ask for? I see you know how to solve this by calculus, brute force and linked the analytic way to do this, and You are not interested in fast nor optimal solution ... this cut down possible answers to zero ... unless you want some different way of solving like using neural network, AI, ...... in such case that makes your question too broad without specs ... – Spektre Jan 22 '19 at 09:32

1 Answers1

2

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.

          image
          PDF download lecture by Ion Petre.
Joseph O'Rourke
  • 4,346
  • 16
  • 25
  • Thanks for your answer! But I don't understand your idea. I'm very surprised that you is a coathor this interesting book. – Vnyemets Jan 18 '19 at 10:33
  • 2
    @Vnyemets: It was a mistake to ask for "best fit line" without explaining in what sense. For least squares, I don't believe the convex hull can help. – Joseph O'Rourke Jan 18 '19 at 11:09
  • Yes, this problem can be solved with linear programming. But where does convex hull algorithm apply to? – Vnyemets Jan 18 '19 at 11:11
  • Least squares is only to find a best fit line in an analytic way. Do I misunderstood the excecise? – Vnyemets Jan 18 '19 at 11:18