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

Fig. 7.3 A line transversal l
to the five sets (each of them
with radius r) exists, hence
the objective function value
of this line satisfies
f max .l/ r

r

r

7.3.4.2 The Finite Dominating Set Property

The main result for minmax hyperplane location is the following blockedness
property .

Theorem 7.7 (FDS for Minmax Hyperplanes) (Schöbel 1999a ; Martini and
Schöbel 1998 , 1999 ; Plastria and Carrizosa 2012 )Let d be derived from a norm
or a gauge and let n D C 1 . Then there exists a minmax hyperplane w.r.t d that
is at the same (maximum) distance from D C 1 affinely independent points. If and
only if the norm or the gauge is smooth, we have that all minmax hyperplanes are
at maximum distance from D C 1 affinely independent points.

Sketch of Proof for Norms Similar to the proof for median hyperplanes we look at
the case for vertical distances first. Here, the objective function is linear as long as
the maximum distance does not change (if n>1). We hence may use a type of
farthest Voronoi diagram in the dual space, i.e., a partition of the dual space into
(not necessarily connected) polyhedral cells

C.v j / WD f .a;b/ W d.H a;b ;v j / d.H a;b ;v/for all v 2 V g
Df .a 1 ;:::;a D1 ;b/ Wj v t j a C b jj v t i a C b j for all i D 1;:::;n g

and it can be shown that an extreme point of such a cell is an optimal solution for
the case of the vertical distance. Note that the cell structure does not change when
we replace the vertical distance by a distance d derived from a norm, since we have

C 0 .v j / WD f .a;b/ W d.H a;b ;v j / d.H a;b ;v/for all v 2 V g
Df .a 1 ;:::;a D1 ;b/ W j v t j a C b j

ı .a/ j v t i a C b j

for all i D 1;:::;n g

ı .a/

D C.v j /;

and using again that the objective function on these cells is quasiconcave, the result
follows.

t