Location of Dimensional Facilities in a Continuous Space - Location Science - page 135

and Rodríguez-Chía 2011 ), a conveyor belt, or a mining shaft (e.g., Brimberg et al.
2002 ). Line location has also been mentioned in connection with the planning of
pipelines, drainage or irrigation ditches, or in the field of plant layout (see Morris
and Norback 1980 ).
In computational geometry , the width of a set is defined as the smallest possible
distance between two parallel hyperplanes enclosing the set (Houle and Toussaint
1985 ). If the set is a polyhedron with extreme points V Df v 1 ;:::;v n g determining
the width of this set is equivalent to finding a hyperplane minimizing the maximum
distance to V . The relation between hyperplane location and transversal theory
is mentioned in Sect. 7.3.4.1 . In machine learning, a support vector machine is a
hyperplane (if it exists) separating red from blue data points and maximizing the
minimal distance to these points (see Bennet and Mangasarian 1992 ; Mangasarian
1999 ). If the set of red and blue points are not linearly separable, one may look for
a hyperplane which minimizes the maximum distance to the points on the wrong
side. This problem can again be solved as a restricted hyperplane location problem,
see Carrizosa and Plastria ( 2008 ) and Plastria and Carrizosa ( 2012 ).
In statistics , classical linear regression asks for a hyperplane which minimizes
the sum of squared vertical distances to a set of data points, while orthogonal
regression (also called total least squares, see Golub and van Loan 1980 ) calls for
a hyperplane minimizing the sum of squared Euclidean distances. However, these
estimators are usually not considered as robust. This gives a reason for computing
L 1 -estimators minimizing the sum of absolute vertical (or orthogonal) differences,
since the median of a set is considered more robust than its mean. We refer to
Narula and Wellington ( 1982 ) for a survey on absolute errors regression. More
general, many robust estimators can be found as optimal solutions to ordered
hyperplane location problems, i.e., hyperplane location problems minimizing an
ordered median objective function (see Chap. 10 for the definition of ordered median
functions). Such problems are treated in Sect. 7.3.6 .Anexampleare trimmed
estimators which neglect the k largest distances assuming that these belong to
outliers. We list some of the most popular estimators and their corresponding
hyperplane location problems in Table 7.1 . For each of them we specify the distance
function d which is used to measure the distance from the data points (i.e., the
existing points) to the hyperplane, and the vector 2

n which specifies the ordered

R

Tabl e 7. 1 Correspondence between line and hyperplane location problems and robust estimators

Estimator Distance Weights of ordered median function

d D d ver Least squares D .1;:::;1/

d D ` 2 Totalleastsquares D .1;:::;1/

d D d ver Least trimmed squares D .1;:::;1;0;:::;0/

Least absolute deviation d D d ver D .1;:::;1/

Least trimmed absolute deviation d D d ver D .1;:::;1;0;:::;0/

d D d ver Least median of squares D .0;:::;0;1;0;:::;0/(n odd)

D .0;:::;0;1;1;0;:::;0/(n even)