Xref: utzoo sci.math:14772 sci.math.num-analysis:1478 sci.math.stat:1896 comp.theory:1461
Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!usc!julius.cs.uiuc.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.190136.4006@noose.ecn.purdue.edu>
Date: 24 Jan 91 19:01:36 GMT
References: <14979@milton.u.washington.edu> <62418@brunix.UUCP>
Sender: news@noose.ecn.purdue.edu (USENET news)
Organization: Purdue University Engineering Computer Network
Lines: 31

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