Geoscience Reference
In-Depth Information
7.4.3
The Minsum Hypersphere Location Problem
We start with the minsum hypersphere location problem. Given a distance d derived
from a norm, the goal is to find a hypersphere S D S x;r which minimizes
X
n
X
n
f 1 .S x;r / D
w j d.S x;r ;v j / D
w j j d.x;v j / r j :
(7.17)
jD1
jD1
The location of a Euclidean circle in the plane has been defined and treated in
Drezner et al. ( 2002 ). This has then been generalized to the location of a norm-circle
in the plane in Brimberg et al. ( 2009b ), and later to the location of a hypersphere with
respect to any norm in
D (Körner et al. 2012 ). The Euclidean case in dimension d
has been also extensively analyzed in Nievergelt ( 2010 ).
We start by presenting some general properties of minsum hypersphere location
problems. In contrast to hyperplanes, it is not obvious in which cases a minsum
hypersphere exists, since a hypersphere can degenerate to a point (for r D 0)andto
a hyperplane (for r !1 ). The following results are known.
R
Lemma 7.6 (Brimberg et al. 2011a ;Körneretal. 2012 )
￿
No hypersphere with r D 0 can be a minsum hypersphere.
￿
For any smooth norm there exist instances for which no minsum hypersphere
exists.
￿
For any elliptic norm and any block norm a minsum hypersphere exists for all
instances with n D C 1 .
Since no optimal solution degenerates to a point, we need not bother with
existence results if we restrict r to an upper bound and solve the problem then.
Let us now discuss the halving property. To this end, we define the set of points
outside, on, and inside the hypersphere
S x;r WDf j 2f 1;:::;n gW d.x;v j />r g
S x;r WDf j 2f 1;:::;n gW d.x;v j /<r g
S x;r WDf j 2f 1;:::;n gW d.x;v j / D r g
and let
W x;r WD X
j2S x;r
w j ;W x;r WD X
j2S x;r
w j ;W x;r WD X
j2S x;r
w j :
As before, let W D P jD1 w j be the sum of all weights.
Search WWH ::




Custom Search