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.