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

Theorem 7.6 (Incidence Property for Minsum Hyperplanes) (Plastria and Car-
rizosa 2001 )Let d be derived from a gauge and let n D . Then there exists
a minsum hyperplane w.r.t the distance d that passes through D 1 affinely
independent points.

Note that this incidence property does not define an FDS.

7.3.4 The Minmax Hyperplane Location Problem

We now turn our attention to the minmax hyperplane location problem in which we
look for a hyperplane H a;b which minimizes

f max .H a;b / D max

jD1;:::;n w j d.H a;b ;v j /:

A hyperplane H minimizing f max .H/ is called minmax hyperplane w.r.t d.Again,
let us assume n>D. Since the main results for the location of minmax hyperplanes
are similar for different types of distance functions, we need not distinguish between
vertical, norm-based and gauge distances here. We start with a link to computational
geometry.

7.3.4.1 Relation to Transversal Theory

Minmax location problems often rely on Helly's theorem (Helly 1923 ). For the
location of hyperplanes, this result can only be applied for the vertical distance,
since the sets f .a;b/ W d.H a;b ;v/ Ǜ g are non-convex in general if d 6D d ver .
Instead, the following relation to transversal theory may be exploited.

D , a hyperplane H is called a

Definition 7.2 Given a family of sets M in R

hyperplane transversal with respect to M if M \ H 6D; for all M 2 M .

Using this definition it is directly clear that f max .H/ r if and only if H is a
hyperplane transversal for the set M Df M j .r/;j D 1;:::;n g with

D W w j d.x;v j / r g :

M j .r/ Df x 2 R

Instead of looking for a hyperplane minimizing the maximum distance to a set
of existing points, we can hence equivalently look for the smallest possible r 0
such that a hyperplane transversal for the sets M j .r/;j D 1;:::;n exists. As an
example, in Fig. 7.3 we search a line minimizing the maximum rectangular distance
to the five given points, each of them with unit weight. Since it is a line transversal
for the five sets M j .r/, the depicted line l satisfies f max .l/ r.