As part of a computational geometry question, I need a result for an intermediate step.
Suppose there is a convex polygon S, with finitely many points inside the polygon. Now, we want to find the line outside the polygon (i.e, the line can pass through a vertex or edge but cannot intersect) which minimizes the sum of perpendicular distances between the line and (vertices + interior points).
I have a hunch that we can prove that this line must be one of the edges, but I am unable to find a proof.
The simplest approach I tried was checking if rotating a line passing through vertex (but outside polygon) always decreases the sum till it reaches the edge. But this is clearly not true.
How to prove this?
Note 1: I think that this theorem must be true, but I have not seen it anywhere. It might be possible that it is actually false and the original question can be solved by a different method. If so, I would like to see a counterexample.
Note 2: The original question, the only answer proposes the theorem but does not provide a proof.
A distance from a point $(x_i,y_i) $ to a line given by the equation $ax+by+c=0 $ is $$ \frac{|ax_i+by_i+c|}{\sqrt {a^2+b^2}}.\tag1 $$
Now because the line is outside of the hull polygon the expression $ax_i+by_i+c$ has the same sign for all points, which we without loss of generality will assume to be positive. Hence we may drop taking the absolute value and write for the sum of distances: $$ D (a,b,c)=\sum_{i=1}^N\frac{ax_i+by_i+c} {\sqrt {a^2+b^2}}=N\frac{aX+bY+c} {\sqrt {a^2+b^2}},\tag2 $$ where $(X,Y) $ are coordinates of the centroid of the points.
Now observe that the right hand side in (2) is nothing else but the multiplied by $N$ distance from the centroid to the line which is indeed minimized by one of the polygon edges, as claimed.