Xref: utzoo sci.math:14779 sci.math.num-analysis:1479 sci.math.stat:1897 comp.theory:1463
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!hellgate.utah.edu!caen!uakari.primate.wisc.edu!samsung!spool2.mu.edu!news.cs.indiana.edu!noose.ecn.purdue.edu!violet.ecn.purdue.edu!ahaas
From: ahaas@violet.ecn.purdue.edu (Alan Haas)
Newsgroups: sci.math,sci.math.num-analysis,sci.math.stat,comp.theory
Subject: Re: Supporting line for N points in 2 space
Message-ID: <1991Jan24.211250.7158@noose.ecn.purdue.edu>
Date: 24 Jan 91 21:12:50 GMT
References: <14979@milton.u.washington.edu> <62418@brunix.UUCP> <1991Jan24.190136.4006@noose.ecn.purdue.edu>
Sender: news@noose.ecn.purdue.edu (USENET news)
Organization: Purdue University Engineering Computer Network
Lines: 51

>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.
********