Xref: utzoo sci.math:15274 sci.math.num-analysis:1573 sci.math.stat:1989 comp.theory:1564
Path: utzoo!attcan!uunet!decwrl!sun-barr!ccut!s.u-tokyo!rkna50!nttlab!utogw!fukuda
From: fukuda@gssm.otsuka.tsukuba.ac.jp (Komei Fukuda)
Newsgroups: sci.math,sci.math.num-analysis,sci.math.stat,comp.theory
Subject: Re: Supporting line for N points in 2 space
Message-ID: <3507@utogw.gssm.otsuka.tsukuba.ac.jp>
Date: 31 Jan 91 03:02:41 GMT
References: <14979@milton.u.washington.edu> <62418@brunix.UUCP>
Sender: news@utogw.gssm.otsuka.tsukuba.ac.jp
Followup-To: sci.math, comp.theory
Organization: GSSM Otsuka, Univ. of TSUKUBA, Tokyo, Japan
Lines: 48

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