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