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

Theorem 7.10 (Halving Property for Minsum Hyperspheres) (Brimberg et al.
2011a ; Körner et al. 2012 )Let S x;r be a minsum hypersphere w.r.t to any distance
derived from a norm. Then

W x;r W
2

and W x;r W
2

(7.18)

Sketch of Proof If we increase the radius from r to r C the distance to points in
S x;r decreases by , and the distance to points in S x;r increases by . This means,
if W x;r > 2 we can improve the objective function by increasing the radius.
(Analogously, if W x;r > 2

we can improve the objective function by reducing

the radius.) t

While the halving property can be nicely generalized, this is unfortunately
not true for the determination of a finite dominating set. The generalization of
Theorem 7.4 would be that there always exists an optimal Euclidean circle passing
through three of the existing points. However, this turned out to be wrong, even in
the unweighted case (see Fig. 7.1 for a counter-example). For most distances it is
not even guaranteed that there exists an optimal circle passing through two points.
The only incidence property that can be shown is the following.

Lemma 7.7 Let d be any distance derived from a norm. Then there exists a minsum
hypersphere w.r.t d which passes through at least one point v 2 V .

Sketch of Proof Let S x;r be a hypersphere. Fix its center point x and assume
without loss of generality that the existing points are ordered such that d.x;v 1 /
d.x;v 2 / ::: d.x;v n /. Then the objective function f 0 .r/ WD f 1 .S x;r / in ( 7.17 )
is piecewise linear in r on the intervals I j WD f r W d.x;v j / r d.x;v jC1 g ,
j D 1;:::;n 1, and hence takes a minimum at a boundary point, i.e., there exists
an optimal radius r D d.x;v j / for some v j 2 V . t

The proof uses that the radius of an optimal circle is the median of the distances
d.x;v 1 /;:::;d.x;v n / which was already recognized in Drezner et al. ( 2002 ).
Not much more can be said in the general case. The only (again, weak) property
into this direction we are aware of is the following:

Lemma 7.8 (Körner et al. 2012 ) Let S D S x;r be a minsum hypersphere with
radius r< 1 .Then S intersects the convex hull of the existing points in at least
two points, i.e., j S \ conv .V/ j 2 .
Furthermore, if j S \ conv .V/ j < 1 ,then S \ conv .V/ V .

7.4.3.1 Location of a Euclidean Minsum Circle

For the Euclidean distance and the planar case D D 2 it is possible to strengthen
the incidence property of Corollary 7.7 .