Xref: utzoo sci.math:14921 sci.math.num-analysis:1507 sci.math.stat:1923 comp.theory:1491
Path: utzoo!censor!geac!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!wuarchive!uunet!brunix!cs.brown.edu!thc
From: thc@cs.brown.edu (Thomas Colthurst)
Newsgroups: sci.math,sci.math.num-analysis,sci.math.stat,comp.theory
Subject: Re: Supporting line for N points in 2 space
Message-ID: <62418@brunix.UUCP>
Date: 24 Jan 91 17:05:17 GMT
References: <14979@milton.u.washington.edu>
Sender: news@brunix.UUCP
Reply-To: thc@cs.brown.edu (Thomas Colthurst)
Organization: Brown Computer Science Dept.
Lines: 18

>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