Geoscience Reference
In-Depth Information
vertical hyperplanes, we again look at the regions R.H ;H / in dual space. On
any such region we obtain that the objective function ( 7.8 ) can be rewritten as
f 1 .H a;b / D X
j2H a;b
C X
jW2H a;b
v t j a C b
k a k ı
v t j a b
k a k ı
w j
w j
0
@ X
j2H a;b
1
w j .v t j a C b/ C X
jW2H a;b
D 1
k a k ı
A ;
w j . v t j a b/
i.e., it is a positive linear function divided by a positive convex function and
hence is quasiconcave. Consequently, it takes its minimum at a vertex of a region
R.H ;H /, i.e., again at a hyperplane passing through D affinely independent
existing points.
t
Note that this theorem has been known for a long time for line location problems
(D D 2) in the case of rectangular or Euclidean distances (Wesolowsky 1972 ,
1975 ; Morris and Norback 1980 , 1983 ; Megiddo and Tamir 1983 ), and has been
generalized to line location problems with arbitrary norms in Schöbel ( 1998 , 1999a )
and to D-dimensional hyperplane location problems with Euclidean distance in
Korneenko and Martini ( 1990 , 1993 ). The extension to hyperplanes with arbitrary
norms is due to Schöbel ( 1999a ) and Martini and Schöbel ( 1998 ).
7.3.3.3
Minsum Hyperplane Location with Gauges
For gauges the results of Theorems 7.4 and 7.3 do not hold any more. There exist
counterexamples showing that optimal hyperplanes need not be halving, see, e.g.,
Schöbel ( 1999a ). However, redefining the halving property by taking into account
the non-symmetry on both sides of a hyperplane, the following similar result [based
on formulation ( 7.6 )] may be transferred to gauge distances.
Theorem 7.5 (Halving Property for Minsum Hyperplanes with Gauges) (Plas-
tria and Carrizosa 2001 )Let d be a gauge and H.a;b/ be a minsum hyperplane
w.r.t. d . Then we have
X
ı .a/ X
j2H a;b [H a;b
w j
w j
ı .a/
j2H a;b
X
ı . a/ X
j2H a;b [H a;b
w j
w j
ı . a/ :
j2H a;b
Also, for gauge-distances it does not hold that there always exists an optimal
minsum hyperplane passing through D of the existing points, for a counterexample
see again Schöbel ( 1999a ). However, the following weaker result holds.
Search WWH ::




Custom Search