[sci.math] Supporting line for N points in 2 space

thc@cs.brown.edu (Thomas Colthurst) (01/25/91)

>Problem:
>	 I have N number of points in 2 space. I have to
>construct a line that is a supporting line to these points ( in
>the sense that all the N points are entirely on one side of the
>line). The constraint is that the sum of the perpendicular
>distances from the N points to this line be a minimum.

The line is obviously going to be a continuation of a segment on the convex hull
of the set of points (the segments which form the minimum convex figure around the
points -- see any elementary text on geometric algorithms for a convex hull
algorithm).  I can't see of any easy way to determine which line minimizes the
constraint, though a number of heuristic tests (the line closest to the "center
of gravity" with some sort of preference given to lines that are parallel to the
"orientation" of the data set).  If anyone can find an algorithm that doesn't
have to test every line on the convex hull, I would be interested in hearing about
it.

-Thomas C

ahaas@violet.ecn.purdue.edu (Alan Haas) (01/25/91)

A mathematical program could be used to model the problem.

  First restate the probelm in the following manner.

   Given points in the plane (x(i),y(i))  i=1,..,n

   Find a line given by ax + by = c such that the sum of distances
of the points to line are minimized and  ax(i) + by(i) <= c i=1,..,n.


    The problem can be formualted in the following way

        using decision variabels d,a,b,c where  
   a,b, and c are the cooefficients for the equation of the line.
d is the summation of all the distances.


                 minimize d
    subject to
                 a**2 + b**2 = 1
                 x(i)a + y(i)b <= c   i=1,..,n
                 d = n*c - [sum over i of] (x(i)a + y(i)b)    


This may not be the easiest thing to solve due to the non-linear term

         a**2 + b**2 = 1
--
********
Alan Haas:  Fun is all the more so when it is shared.
********

ahaas@violet.ecn.purdue.edu (Alan Haas) (01/25/91)

>A mathematical program could be used to model the problem.
> 
> First restate the probelm in the following manner.
>
   Given points in the plane (x(i),y(i))  i=1,..,n
>
>  Find a line given by ax + by = c such that the sum of distances
>of the points to line are minimized and  ax(i) + by(i) <= c i=1,..,n.
>
>
>   The problem can be formualted in the following way
>
>       using decision variabels d,a,b,c where  
>  a,b, and c are the cooefficients for the equation of the line.
>d is the summation of all the distances.
>
>
>                minimize d
>   subject to
>                a**2 + b**2 = 1
>                x(i)a + y(i)b <= c   i=1,..,n
>                d = n*c - [sum over i of] (x(i)a + y(i)b)    
>
>
>This may not be the easiest thing to solve due to the non-linear term
>
>         a**2 + b**2 = 1

    This problem is easier to solve than what I had believed.

    Using the obsevation that the optimal line must pass through one of
the points, for each point (x(i),y(i)), find the line that goes through
the point that meets the criteria and minimizes the sum of the distances.
The minimum from comparing the solution of each point will be the answer.

    To solve for a given point, one variable can be eliminated by using

         a**2 = 1 - b**2.

   Let (z1,z2) be the point in question. Use c = az1 + bz2. to eliminate
another varible.

      Now d reduces to an optimization problem of one variable.

  Which means the problem reduces to solving n optimization problems of
one variable and taking the best solution.

--
********
Alan Haas:  Fun is all the more so when it is shared.
********

fukuda@gssm.otsuka.tsukuba.ac.jp (Komei Fukuda) (01/31/91)

In article <62418@brunix.UUCP>, thc@cs.brown.edu (Thomas Colthurst) writes:
> >Problem:
> >	 I have N number of points in 2 space. I have to
> >construct a line that is a supporting line to these points ( in
> >the sense that all the N points are entirely on one side of the
> >line). The constraint is that the sum of the perpendicular
> >distances from the N points to this line be a minimum.
> 
> The line is obviously going to be a continuation of 
> a segment on the convex hull of the set of points 

I believe this is true, but I don't think it is so obvious.
Do you have a simple proof?  The only proof I can imagine
is to use a similar mathematical formulation as
the one posted by Alan Haas

   Given points in the plane p(i)=(x(i),y(i))  i=1,..,n
   assuming (w.l.g.) the origin is in the interior of 
   ConvHull[p(1)..p(n)]

                 minimize  d / Sqrt[a**2 + b**2]
    subject to
                 x(i)a + y(i)b <= 1   i=1,..,n
                 d = n - [sum over i of] (x(i)a + y(i)b)    

and show that the optimal value is attained at a vertex
of the associated convex polyhedron ( x(i)a + y(i)b <= 1,  i=1,..,n).  
Such a vertex corresponds to a segment of the convex hull.  
We have to be careful that the objective function is 
not even concave. (Yet the contours have nice shapes.) 

This proof works in general dimension, but
certainly, this is not simple...

> If anyone can find an algorithm that doesn't
> have to test every line on the convex hull, 
> I would be interested in hearing about it.
> 
> -Thomas C

I suppose the problem is of enumerative nature, and one
has to check all of the lines.  

--
Komei Fukuda
Grad. Sch. of Systems Management   Tel: +3-3942-6876 
University of Tsukuba, Tokyo       Fax: +3-3942-6829 
Bunkyo-ku, Tokyo 112, JAPAN        Email:fukuda@gssm.otsuka.tsukuba.ac.jp