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.

  • $\begingroup$ "... rotating a line passing through vertex (but outside polygon) always decreases the sum till it reaches the edge. But this is clearly not true." For which point arrangements is this not true? $\endgroup$
    – user
    Feb 26 at 8:13
  • $\begingroup$ For almost all arrangements. Like if you rotate the line, you have split the plane into regions based on the perpendicular bisectors. Points lying in some regions can have their sum increased. $\endgroup$ Feb 26 at 11:30
  • $\begingroup$ According to my analysis it cannot happen. The maximum distance sum is achieved if the line passing through a vertex is drawn perpendicular to the direction pointing to the centroid. Any rotation from this position will decrease the sum of distances. $\endgroup$
    – user
    Feb 26 at 11:46
  • $\begingroup$ What you said is correct, but it doesn't imply that it should continually keep decreasing till it reaches the edge. In other words, the function may not be monotonic. Maybe I'm just messing something up, but it isn't obvious to me. $\endgroup$ Feb 27 at 6:16
  • $\begingroup$ Check your calculation. Until the line intersects the polygon the distance sum is proportional to the sine of the angle between the line and the direction to the centroid, and sine is a monotonic function on $[0,\pi/2]$. $\endgroup$
    – user
    Feb 27 at 7:55

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.